When Do I Need Strong Induction vs Weak Induction?

The textbook line is that strong induction and ordinary (weak) induction are logically equivalent — any statement provable with one is provable with the other. That is true, and it is also not the answer you want when you are stuck in the middle of a problem at 11pm. The real question is practical: which form will let me finish this proof without rewriting the statement?

The short answer is about reach. Weak induction gives you one step of history — you assume P(k) and derive P(k+1). Strong induction gives you all of history — you assume P(1), P(2), \dots, P(k) and derive P(k+1). If the natural argument for P(k+1) points backwards only one step, weak is fine. If it points backwards two, three, or an unknown number of steps, strong is the right tool.

The two forms side by side

Weak induction. Prove P(1). Prove: for every k \geq 1, P(k) \Rightarrow P(k+1). Conclude P(n) for all n \geq 1.

Strong induction. Prove P(1). Prove: for every k \geq 1, [P(1) \wedge P(2) \wedge \dots \wedge P(k)] \Rightarrow P(k+1). Conclude P(n) for all n \geq 1.

Why they are logically equivalent: if you can prove P(k+1) using only P(k), you can certainly prove it using all of P(1), \dots, P(k) — you just ignore the extra hypotheses. Going the other way, if you have a strong-induction proof, you can convert it into a weak-induction proof by replacing P(n) with the stronger statement Q(n) = P(1) \wedge P(2) \wedge \dots \wedge P(n). Weak induction on Q does the same work as strong induction on P. Equivalence does not mean interchangeability without effort — one form is often dramatically more convenient than the other.

The signal that tells you to switch to strong induction

While attempting the inductive step, ask yourself: how far back does my argument reach?

If P(k+1) follows from P(k) alone — weak is enough.
If P(k+1) follows from P(k) and P(k-1) — weak will not work directly; use strong.
If P(k+1) follows from some earlier P(m) where m < k but the exact value of m depends on k — definitely strong.
If the recursion jumps around (halving, doubling, splitting into two smaller problems) — strong, always.

A weak-induction problem

Prove 1 + 2 + \dots + n = \dfrac{n(n+1)}{2}.

The inductive step: assume 1 + 2 + \dots + k = \dfrac{k(k+1)}{2}, add k+1 to both sides, simplify to \dfrac{(k+1)(k+2)}{2}. You used only P(k). Weak induction is the right tool.

A strong-induction problem: the Fibonacci sequence

Let F_1 = 1, F_2 = 1, and F_{n+2} = F_{n+1} + F_n for n \geq 1. Claim: F_n < 2^n for every n \geq 1.

Try weak induction. Assume F_k < 2^k. You want to show F_{k+1} < 2^{k+1}. But F_{k+1} = F_k + F_{k-1}, so you need a bound on F_{k-1} as well — and weak induction only hands you F_k. You are stuck.

Switch to strong induction. Assume F_i < 2^i for every i \leq k. Now:

F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^k + 2^k = 2^{k+1}.

The proof goes through because you had access to both P(k) and P(k-1) at once. Base cases: you verify F_1 = 1 < 2 and F_2 = 1 < 4. Two base cases are needed because the recursion reaches back two steps.

Another strong-induction signal: prime factorisation

Prove that every integer n \geq 2 is a product of primes.

Inductive step (strong form): let k \geq 2, and assume every integer m with 2 \leq m \leq k is a product of primes. Consider k+1. Either k+1 is prime (done) or k+1 = a \cdot b with 2 \leq a, b \leq k. By the strong hypothesis, both a and b are products of primes, so k+1 is too.

Weak induction cannot do this cleanly. When you factor k+1 as a \cdot b, the factors a and b can be anywhere between 2 and k — you have no idea which specific value — so you cannot invoke a hypothesis about just one previous index. Strong induction reaches into all of history, which is exactly what the problem requires.

The deeper pattern: "divide into smaller pieces"

Any proof that proceeds by splitting the (k+1)-case into one or more smaller cases — without guaranteeing that the smaller cases are exactly P(k) — will want strong induction. Examples:

Binary trees. Prove that a binary tree with n internal nodes has n+1 leaves. A tree with k+1 nodes has a root plus two subtrees, each with at most k nodes. You induct by applying the hypothesis to each subtree — and the subtrees can be of any size up to k.
Division with remainder. Prove the uniqueness of the quotient-remainder decomposition. The inductive argument reduces to a smaller dividend, whose size you cannot predict exactly.
The game of Nim. Proving which positions are winning requires assuming the hypothesis for every position with fewer total stones — again, a strong-induction structure.

The common thread: the "k+1 case" is not reached from the "k case" by adding one more element. It is reached by breaking into smaller pieces of unknown size. Weak induction marches in lockstep; strong induction allows jumps.

Do not forget the base cases

The number of base cases you need matches the reach of the recursion. If the inductive step reaches back d steps, you need at least d base cases to prevent the argument from leaning on unverified ground.

Ordinary linear recursion (P(k) \Rightarrow P(k+1)): one base case.
Second-order recursion like Fibonacci (P(k-1) and P(k) imply P(k+1)): two base cases.
Strong induction where the recursion can reach arbitrarily far back: one base case P(1) is usually enough, because the strong hypothesis is trivially true for k = 1 (there are no previous indices to worry about, so the implication is vacuous above the base).

The practical rule

Start with weak induction. If you find yourself wanting a bound on P(k-1) or P(m) for some earlier m during the inductive step, pause and switch to strong induction. There is no penalty for using strong induction when weak would have sufficed — the extra hypotheses just go unused. The only time strong induction is wrong is when you forget to prove enough base cases to support the reach of your inductive step.

In practice, strong induction is the safer default for any proof that involves divisibility, factoring, recursion with multiple previous terms, or splitting a structure into smaller sub-structures. For counting formulas, straightforward summation identities, and anything where the (k+1)-case is obtained by adding one new term, weak induction is cleaner and more natural.