Strong induction and the well-ordering principle

Ordinary induction proves \( P(n+1) \) from \( P(n) \) alone. Strong induction allows the inductive step to use every earlier case: to prove \( P(n) \) for all \( n \ge n_0 \), prove the base cases, then prove that if \( P(n_0), P(n_0 + 1), \dots, P(k) \) all hold then \( P(k+1) \) holds. It is not a stronger principle (the two are equivalent), but it is the natural tool whenever the step from \( k+1 \) reaches back more than one place.

The standard example is factorisation. Claim: every integer \( n \ge 2 \) is a product of primes. If \( n \) is prime, it is a product of one prime. Otherwise \( n = ab \) with \( 2 \le a, b < n \), and by the strong hypothesis both \( a \) and \( b \) are products of primes, so \( n \) is too. Ordinary induction would be stuck here, because knowing about \( n - 1 \) says nothing about the factors of \( n \). Another: every amount of postage of at least 8 cents can be made with 3 and 5 cent stamps. Check 8, 9 and 10 directly; for \( n \ge 11 \), make \( n - 3 \) (by hypothesis, since \( n - 3 \ge 8 \)) and add one 3 cent stamp. Three base cases are needed because the step reaches back three places.

Recursive definitions and strong induction go together. The Fibonacci numbers are \( F_1 = F_2 = 1 \) and \( F_{n} = F_{n-1} + F_{n-2} \); the example computes \( F_{20} = 6765 \). Any claim about them, such as \( F_n < 2^n \), is proved with two base cases and a step that uses both of the two previous values: \( F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^{k+1} \).

The well-ordering principle says every non-empty set of natural numbers has a least element. It is equivalent to induction and gives a different way to write the same proofs: suppose the claim fails, take the smallest counterexample, and show that a smaller one exists. For instance, if some integer \( n \ge 2 \) had no prime divisor, the smallest such \( n \) is not prime, so it has a divisor \( a \) with \( 1 < a < n \); \( a \) has a prime divisor by minimality, and that prime divides \( n \).

Picture it: ordinary induction is a line of dominoes, each knocked over by the one just before. Strong induction is a line where each domino is pushed by the whole crowd of dominoes already fallen. The smallest counterexample is the first domino left standing, and the proof shows the crowd behind it would have knocked it down.

Think it: count the base cases by asking how far back the inductive step reaches. A step that uses \( P(k - 2) \) must not be applied to a \( k \) for which \( k - 2 \) is below the starting point, so those small cases have to be checked by hand. Missing a base case is the most common way a strong induction proof fails.