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.

Top left: domino P(1) is pushed, the base case. Top right: domino P(k) leans on P(k+1), the inductive step, with a green implication arrow under each pair. Bottom: a row of eight green dominoes that have all fallen, continuing as P(n) for all n
The base case pushes the first domino; the step makes each domino knock over the next. Together every domino falls.

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

  1. Base case: check P(n₀) directly, usually by plugging in the number. This pushes the first domino.
  2. 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

Three rows of dominoes. First: the first domino is red because P(1) is false, and none fall. Second: domino 1 lies flat in a wide gap and dominoes 2 onward stand. Third: dominoes 1, 2 and 3 stand while dominoes 4 onward have fallen
No base: nothing falls. A gap: the chain stops there. A later start: only the dominoes from n₀ on are proved.
ClaimBaseStepWhat falls
1 + … + n = n(n+1)/2✓ P(1)✓ every k ≥ 1all
n² + n is odd✗ 2 is even✓ every k ≥ 1nothing
any n horses have one colour✓ P(1)✗ at k = 1domino 1 only
2ⁿ ≥ n², n ≥ 4✓ P(4): 16 ≥ 16✓ every k ≥ 34, 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.

Another proof style: Cantor's diagonal argument flips digit n of row n to build a sequence that no list can hold.

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).

On the mind map

This page on the Logic, Sets & Counting mind map · 13 pages in 4 branches · open it to see the whole map and test yourself in recall mode.