The idea: a row of dominoes
A proof by induction shows that a statement P(n) is true for every whole number n from some start n₀ on. Picture an endless row of dominoes, one for each n. You cannot knock each one over by hand, there are infinitely many. But two facts are enough: the first domino is pushed, and every domino is close enough to knock over the next. Then all of them fall.
Pick a claim, then press Check Base, Prove Step and Push; Push runs whatever was not done yet. Under each pair of dominoes a ? turns into a green ⇒ where the step works, or a red ✗ where it fails. Under each domino you see whether its statement got proved.
The two parts of every induction proof
- Base case: check P(n₀) directly, usually by plugging in the number. This pushes the first domino.
- Inductive step: take any k ≥ n₀, assume P(k) is true (the inductive hypothesis), and derive P(k+1) from it. This shows the gap between any two neighbours is small enough.
Then P(n) holds for every n ≥ n₀. Note what the step does not claim: it does not say P(k) is true. It only says "if P(k), then P(k+1)". The truth comes from the base case and travels along the row one domino at a time.
Worked example: 1 + 2 + … + n = n(n+1)/2
Base: for n = 1 the left side is 1 and the right side is 1·2/2 = 1. Step: assume 1 + … + k = k(k+1)/2. Add k+1 to both sides: 1 + … + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2. That is exactly P(k+1), the formula with k+1 in place of n. On the canvas every domino falls, and each one shows the check, for example 1 + 2 + 3 + 4 = 10 = 4·5/2 (Demo: sum formula → every domino falls). The same formula has a picture proof on Proofs Without Words; induction turns such a picture into a proof for every n.
What goes wrong without each part
| Claim | Base | Step | What falls |
|---|---|---|---|
| 1 + … + n = n(n+1)/2 | ✓ P(1) | ✓ every k ≥ 1 | all |
| n² + n is odd | ✗ 2 is even | ✓ every k ≥ 1 | nothing |
| any n horses have one colour | ✓ P(1) | ✗ at k = 1 | domino 1 only |
| 2ⁿ ≥ n², n ≥ 4 | ✓ P(4): 16 ≥ 16 | ✓ every k ≥ 3 | 4, 5, 6, … |
A step without a base proves nothing. If k² + k is odd, then (k+1)² + (k+1) = (k² + k) + 2(k+1) is odd plus even, so odd. The step is correct! But 1² + 1 = 2 is even, and in fact n² + n = n(n+1) is always even. The dominoes are perfectly spaced and nobody pushes the first one (Demo: step but no base).
The step must work for every k. The famous false proof that all horses have one colour: one horse has one colour; for k+1 horses, the first k share a colour and the last k share a colour, and the two groups overlap, so all k+1 match. The overlap is the flaw. For k = 1 the groups are {horse 1} and {horse 2}, which share nobody. One broken link, between domino 1 and domino 2, and the whole chain stops (Demo: all horses one colour → gap at 1 → 2).
The base can start anywhere. 2ⁿ ≥ n² is false at n = 3 (8 < 9), so the claim starts at n₀ = 4: 2⁴ = 16 ≥ 16. The step uses 2ᵏ⁺¹ = 2·2ᵏ ≥ 2k² and needs 2k² ≥ (k+1)², which holds for k ≥ 3. Push domino 4 and dominoes 4, 5, 6, … fall; dominoes 1 to 3 stay up because the proof says nothing about them (Demo: 2ⁿ ≥ n² starts at n = 4).
Why it works, and strong induction
Suppose the base and the step hold but some P(n) is false. Take the smallest such n. It is not n₀, since the base holds, so P(n−1) is true, and the step then gives P(n): a contradiction. This argument uses the well-ordering principle: every non-empty set of whole numbers has a smallest element.
Strong induction lets the step assume P(n₀), …, P(k) all at once, not only P(k). It proves the same things, but it is handier when P(k+1) depends on a much earlier case, for example "every n ≥ 2 is a product of primes": n = a·b with smaller a and b, which are not n − 1.
Where it shows up in computing
- Recursion: a recursive function is correct if its base case is right and each call is correct assuming the smaller calls are. That is induction on the input size; Towers of Hanoi calls it the recursive leap of faith and needs 2ⁿ − 1 moves, which induction proves.
- Loop invariants: an invariant true before the first iteration (base) and kept by each iteration (step) is true when the loop ends.
- Counting: closed forms such as the geometric sum 1 + r + … + rⁿ (see Geometric Series) and recurrences such as the Catalan numbers (Catalan Numbers) are proved this way.
Other proof styles on this site: the pigeonhole principle proves existence by the worst case, and Truth Tables and Sets proves De Morgan's law by checking every row.
What the page leaves out
Structural induction on trees, lists and formulas; induction on two variables; transfinite induction; formal proofs in a proof assistant; the Peano axioms that make induction an axiom of the whole numbers; and inductions that need a stronger statement than the one asked for (loading the hypothesis).
See where this page fits on the Logic, Sets & Counting mind map.