strong induction

Ordinary induction lets you assume the statement for n and prove it for n+1 — each domino leans on exactly the one before it. But sometimes a case depends not on the immediately previous case but on several earlier ones, or on a case roughly half its size. Strong induction widens the hypothesis: to prove P(n), you may assume P(k) for all smaller k at once, not just k = n-1. It is as if each domino can be knocked over by any combination of the dominoes before it.

Formally, to prove 'P(n) for all n >= n0', strong induction lets you prove P(n) using the assumption 'P(k) holds for every n0 <= k < n'. (Often no separate base case is even needed, because the smallest n has no smaller k, so the hypothesis is empty and you must establish that case outright.) A classic example: every integer n >= 2 has a prime factorization. If n is prime, done. If n = a*b with 1 < a, b < n, then by the strong hypothesis both a and b already factor into primes, so n does too. Note we used the result for two numbers smaller than n, neither necessarily n-1 — exactly what ordinary induction would not give us.

Strong induction is the natural tool for divide-and-conquer and recursive algorithms, where solving size n calls subproblems of size n/2, or n-1 and n-2, or any smaller sizes. Proving such a procedure correct typically says 'assume the recursive calls are correct on all smaller inputs (the strong hypothesis), then show the combine step is correct.' It is no more powerful than ordinary induction in principle — each can simulate the other — but it is far more convenient when a case leans on many or far-away smaller cases.