Explainer
Stepping Through Simple Induction Drills
Push the first domino and watch the rest fall.
Induction is a proof pattern for claims about every whole number. You prove two things. First, the claim holds for the starting case. Second, if it holds for any number k, it also holds for k + 1. Together these cover every case, the way one domino knocking over the next knocks over the whole line.
Here is a claim to test. For every whole number n ≥ 1, the sum 1 + 2 + ... + n equals n(n+1)/2. Before you touch the algebra, guess whether it is true. Then run the two steps yourself. Do not peek at the steps below until you have tried.
Worked Example · Induction
Summing the first n integers
Problem
Prove that 1 + 2 + ... + n = n(n+1)/2 for every whole number n ≥ 1.
Steps
- 1.Base case: at n = 1, the left side is 1 and the right side is 1(2)/2 = 1. They match.—Always start with the smallest case the claim names. If this fails, the whole proof fails.
- 2.Assume the claim holds for some k: 1 + 2 + ... + k = k(k+1)/2.—This is the inductive hypothesis. You assume it only for one k, and you do not assume it for all k.
- 3.Add (k+1) to both sides: 1 + ... + k + (k+1) = k(k+1)/2 + (k+1).—You are building the k+1 case out of the k case.
- 4.Factor the right side: (k+1)(k/2 + 1) = (k+1)(k+2)/2.—This is the target form for n = k+1, so the step lands where it must.
- 5.Conclude the claim holds for k+1. With the base case, it holds for all n ≥ 1.—The chain of implications is the proof. Write this sentence out every time.
The takeaway
Induction needs both the base case and the step. A true step with no base case proves nothing.
Quiz
1/2
1
Statement
If you verify the claim for n = 1 through n = 100 by hand, the induction proof is complete.
If you verify the claim for n = 1 through n = 100 by hand, the induction proof is complete.
You answered:FALSE
Incorrect
Why it's false
Checking many cases does not cover infinitely many. The step argument is what carries the proof past any case you did not check.
2
Statement
In the inductive step, you assume the claim is true for k and show it is true for k+1.
In the inductive step, you assume the claim is true for k and show it is true for k+1.
You answered:FALSE
Incorrect
Why it's true
That is the structure of the step. The assumption applies to one arbitrary k, and the conclusion is about k+1.
Match the Terms
0/4
Part of the proof
What it does
Choose
