Strong Induction and Well-Ordering

Strong induction is simply induction where, to prove the next case, you're allowed to use all the cases before it, not just the one right before. It's called "strong" because the assumption you get to make is stronger, though it turns out it can't prove anything ordinary induction can't; it just makes many proofs far easier to write. It's the natural tool whenever a problem breaks into smaller pieces of unpredictable size. The formula above, $n = p_1 p_2 \cdots p_m$, says something you already believe: any whole number $n$ (at least 2) can be written as primes $p_1, p_2, \dots$ (they may repeat) multiplied together, $m$ of them in all. We'll prove it in a few lines.

Strong induction: to prove $S(n)$ for all $n \ge n_0$, prove the base case(s), then show that if $S(n_0), S(n_0 + 1), \dots, S(k)$ are all true, so is $S(k + 1)$. Think of the dominoes again, except now each domino is knocked over by the whole row behind it, not just its neighbor. Since every earlier domino has already fallen, that's perfectly fair.

Factoring into primes. If $k + 1$ is prime, it's already a product of primes. Otherwise $k + 1 = ab$ with $2 \le a, b \le k$. By the strong hypothesis both $a$ and $b$ are products of primes, and so is their product. Notice why ordinary induction wouldn't help here: knowing how to factor $k$ says nothing about $k + 1$'s factors. $k + 1 = 36$ splits as $6 \cdot 6$ or $4 \cdot 9$, and neither has anything to do with 35. You need to reach back to whatever smaller numbers show up.

Postage stamps. Every amount of at least 12¢ can be made from 4¢ and 5¢ stamps. Check the four base cases $12 = 4+4+4$, $13 = 4+4+5$, $14 = 4+5+5$, $15 = 5+5+5$. For $k + 1 \ge 16$, the amount $k - 3 \ge 12$ can be made by hypothesis; add a 4¢ stamp. Why four base cases? The step always reaches back 4 cents, so 16 leans on 12, 17 on 13, 18 on 14 and 19 on 15. If you'd only checked 12, the chain starting at 13 would never get going.

Well-ordering principle: every nonempty set of positive integers has a smallest element. That sounds too obvious to bother saying, but it's equivalent to induction, and it powers "minimal counterexample" proofs: if a statement failed somewhere, consider the smallest failure and show a smaller one exists. That's a contradiction, the method from two lessons ago, so there's no failure at all.

Divide-and-conquer algorithms such as merge sort and quicksort are proved correct by strong induction on the size of the input.