Strong Induction

Sometimes one previous case is not enough. Ordinary induction gives you the truth at $k$ and asks you to push to $k+1$. But what if the proof of $P(k+1)$ needs $P(k - 5)$ as well? Or, worse, what if $k+1$ factors into two pieces, neither of which is exactly $k$? Strong induction — also called complete or course-of-values induction — lets you assume $P(j)$ for all $j$ strictly less than $k$ when proving $P(k)$. The change in hypothesis is small in print but huge in practice: prime factorisations, Fibonacci-style recurrences, and the postage-stamp theorem all collapse out almost instantly once you can reach back to any earlier case.

The principle

Strong induction proves $\forall n \geq n_0,;P(n)$ by showing one thing: for every $k \geq n_0$, if $P(j)$ holds for every $j$ with $n_0 \leq j < k$, then $P(k)$ holds.

That single conditional packs in both halves of ordinary induction. When $k = n_0$, the range $n_0 \leq j < n_0$ is empty, so the hypothesis is vacuously true — meaning the proof of $P(n_0)$ must stand on its own (this is your "base case"). For larger $k$, you have the full library of earlier truths to pull from.

Worked example: prime factorisation exists

Claim: every integer $n \geq 2$ can be written as a product of one or more primes.

Proof (strong induction on $n$). Let $k \geq 2$ and assume every integer $j$ with $2 \leq j < k$ is a product of primes.

Case 1: $k$ is prime. Then $k$ itself is a product of primes (a one-factor product).

Case 2: $k$ is composite. Then $k = a \cdot b$ with $2 \leq a, b < k$. By the strong hypothesis applied to $a$ and to $b$, each is a product of primes. Multiplying the two products gives $k$ as a product of primes. $\blacksquare$

Why does ordinary induction stumble here? Because $a$ and $b$ are typically not $k - 1$. Ordinary induction only gives you $P(k-1)$; strong induction gives you $P(a)$ and $P(b)$.

Logical equivalence

Strong induction is logically equivalent to ordinary induction: anything one can prove, the other can prove. (Sketch: let $Q(n)$ be "$P(j)$ holds for all $j \leq n$." Then proving $Q$ by ordinary induction is the same as proving $P$ by strong induction.) The choice between them is a matter of convenience, not power. Whenever you find yourself wanting to invoke $P(k - 2)$ or $P(\lfloor k/2 \rfloor)$ inside an inductive step, switch to strong induction and the proof reads naturally.

Pause and think: in the prime-factorisation proof, where did we use that $a, b < k$ (rather than $a, b \leq k$)? What would happen if the hypothesis only covered $j < k$ but the decomposition gave $k = k \cdot 1$?

Strong induction in action

The widget below steps through three classic strong-induction proofs side by side — $F_n \leq 2^n$ (Fibonacci), the prime-factorisation theorem, and the postage-stamp problem. Watch how the inductive step reaches back to two earlier values (or to any earlier value) — that is the move that ordinary induction cannot make.

Try it

• Predict: which integers $\geq 8$ can be paid using 3-cent and 5-cent stamps? Check $8, 9, 10, 11, 12$ by hand. Then prove by strong induction that every $n \geq 8$ works.
• On paper, verify the strong-induction step for $F_n \leq 2^n$ (where $F_n$ is Fibonacci) at $k = 5, 6, 7$. At each $k$ you need BOTH $F_{k-1}$ and $F_{k-2}$, not just $F_{k-1}$ — that is exactly where strong induction kicks in. (The widget above demonstrates ordinary induction on $1 + 2 + \cdots + n = n(n+1)/2$; treat that as a separate example of the cascade.)
• Factor $84$ into primes by repeatedly applying the recursive structure of the proof: split off any factor, recursively factor each piece.
• Before reading the solution: why isn't ordinary induction enough to prove every integer $\geq 2$ is divisible by some prime? Try to write the ordinary-induction step and see where it breaks.

A trap to watch for

The most common slip with strong induction is forgetting to verify the base case explicitly. Because the principle is often phrased as a single conditional — "if $P(j)$ holds for all $j < k$ then $P(k)$" — students sometimes think the base case is taken care of automatically by the empty-range vacuity at $k = n_0$. It isn't. When $k = n_0$ you must still prove $P(n_0)$ from no assumptions. Vacuity gives you nothing to use; it just means the implication doesn't demand anything of you, leaving you face-to-face with $P(n_0)$ directly. Always isolate and verify the base case before settling in for the recursive step. A second trap: conflating strong induction with "assume $P$ holds for finitely many earlier values you happen to know." The hypothesis is $P(j)$ for every $j < k$ — not a hand-picked subset.

What you now know

You can state and apply the principle of strong induction, decide when it is needed (whenever the inductive step references a previous case that isn't $k - 1$), and write the canonical strong-induction proof of the existence of prime factorisations. In the next section we use induction once more to construct closures stage by stage and to prove they are the smallest sets with the required property.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §6.4.
• Knuth, D. E. (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed.). Addison-Wesley, §1.2.1.
• Hammack, R. H. (2018). Book of Proof (3rd ed.). Virginia Commonwealth University, ch. 10.
• Pierce, B. C., et al. (2018). Software Foundations, Vol. 1: Logical Foundations. Online, ch. "Induction."
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, ch. 4.