Strong Induction as a Jenga Tower — Each Block Rests on Many Below

Ordinary induction is a ladder — each rung rests on the single rung immediately below. Strong induction is a Jenga tower — each block rests on all the blocks beneath, not just the previous one. When you are trying to prove P(k+1), strong induction lets you invoke any of P(1), P(2), \dots, P(k) as already-established facts, rather than only P(k).

This extra freedom changes what kinds of statements you can prove. Some statements have a recursive structure where P(k+1) depends on P(k) and P(k-3) simultaneously, or on P(k/2) when k is even. Ordinary induction cannot reach into that history; strong induction can.

The visualisation below shows a Jenga-style tower where you can drag the current block upward and see how many lower blocks are supporting it.

The tower visualisation

Current proof target P(k+1) at block: strong ordinary

A tower of blocks $P(1), P(2), \dots, P(12)$. The orange block is the statement you are currently proving. Green lines point to every block available as an inductive hypothesis. Under *strong* induction, all lower blocks are available. Under *ordinary* induction, only the block immediately below can be cited. Watch the green supporters vanish as you toggle the mode.

Why strong induction is strictly stronger

Read the name carefully: "strong" induction does not mean "more powerful in theorem-proving sense," because strong and ordinary induction can prove exactly the same set of theorems (they are logically equivalent — either can be derived from the other). "Strong" refers to the inductive hypothesis you are allowed to use.

Ordinary induction. Hypothesis: P(k). Goal: P(k+1). You get one prior statement to use.
Strong induction. Hypothesis: P(1), P(2), \dots, P(k) all hold. Goal: P(k+1). You get all prior statements to use.

Both are valid proof techniques. Strong induction is often more convenient because you do not have to anticipate which specific prior P(j) the argument needs — you just have them all available.

Why strong induction is equivalent to ordinary induction even though it looks more generous: if you have proved P(k+1) using the fact that all of P(1), \dots, P(k) hold, you can imagine defining a new predicate Q(k) = P(1) \land P(2) \land \dots \land P(k). Then the strong-induction argument on P is equivalent to an ordinary-induction argument on Q. So any theorem provable by strong induction is also provable by ordinary induction, possibly with a reworked statement. The strength is in convenience, not in reach.

A statement that cries out for strong induction

The classic example is: "every integer n \geq 2 is a product of primes."

Base case. n = 2 is a prime, so it is trivially a product of primes (itself).

Inductive step (strong). Assume every integer j with 2 \leq j \leq k is a product of primes. Show k + 1 is a product of primes.

Two cases:

If k + 1 is prime, we are done — it is a product of primes (just itself).
If k + 1 is composite, write k + 1 = ab where 2 \leq a, b \leq k. By the strong inductive hypothesis, a is a product of primes and b is a product of primes. Multiplying, k + 1 = ab is a product of primes.

Notice what happened in the composite case. You invoked the hypothesis at a and at b, which are both less than k + 1 but not necessarily equal to k. You could have k = 14 and k + 1 = 15 = 3 \cdot 5 — then you need P(3) and P(5), not P(14). Ordinary induction only gives you P(14). Strong induction gives you P(3) and P(5) directly, with no setup needed.

This is the signature: the recursive decomposition lands you on smaller indices that are not the immediate predecessor. Whenever that happens, reach for strong induction.

Another example: the Fibonacci sequence

Define F_1 = 1, F_2 = 1, and F_n = F_{n-1} + F_{n-2} for n \geq 3. A common claim to prove: F_n \leq 2^{n-1} for all n \geq 1.

Base cases. F_1 = 1 \leq 2^0 = 1. F_2 = 1 \leq 2^1 = 2. Both hold.

Inductive step (strong). Assume F_j \leq 2^{j-1} for all j \leq k, with k \geq 2. Show F_{k+1} \leq 2^k.

F_{k+1} = F_k + F_{k-1} \leq 2^{k-1} + 2^{k-2} = 2^{k-2}(2 + 1) = 3 \cdot 2^{k-2} \leq 4 \cdot 2^{k-2} = 2^k.

Here the inductive step uses both P(k) (for F_k \leq 2^{k-1}) and P(k-1) (for F_{k-1} \leq 2^{k-2}). Ordinary induction only hands you P(k); to get P(k-1) you would need an additional trick. Strong induction just gives you both.

The structural signal is the recurrence F_n = F_{n-1} + F_{n-2}: whenever a recurrence uses more than one previous term, strong induction is the natural hammer.

Two base cases are common

A detail worth flagging: strong-induction arguments often require multiple base cases. In the Fibonacci example, you verified P(1) and P(2) separately — because the inductive step from P(2) to P(3) uses P(1) in the hypothesis, and if P(1) had not been checked, the step would rest on unverified ground.

A rule of thumb: if your inductive step uses the hypothesis at indices as far back as k - c for some constant c, you need c + 1 base cases — one for each of P(1), P(2), \dots, P(c+1). The Fibonacci recurrence looks back 2 steps, so c = 1 and you need 2 base cases.

What the tower says about real proofs

The Jenga tower makes three things visible:

The support available to P(k+1) is the entire history P(1), \dots, P(k), not just P(k).
Which lower statements you actually use depends on the recursive structure of the problem. Some problems use only P(k); others use P(k-1); others use all of them.
The number of base cases you need is determined by how far back the inductive step reaches. The further back, the more foundation blocks you need to lay directly.

When you are stuck on an induction proof because "P(k) alone does not give me what I need," the move is almost always to strong induction. Give yourself the whole tower and see which blocks fit.

The one-line takeaway

Strong induction is the same game as ordinary induction, but with every previously-proved statement on the table. Use it whenever the recursive structure of your problem lands on indices that are not just the immediate predecessor.