Strong Induction Explained: Principle, Examples and vs Weak

Strong induction beefs up ordinary induction: where weak induction assumes P(k) to prove P(k+1), strong induction assumes all of P(1), P(2), …, P(k). That extra ammunition matters whenever P(k+1) depends on smaller cases further back than k.

The classic example is "every integer n ≥ 2 is a product of primes": factoring k+1 as a·b may need the hypothesis at a and b, far below k. Weak induction cannot reach them; strong induction can.

Key Concepts

• Strong inductive hypothesis: assume P(j) is true for every j with 1 ≤ j ≤ k (or over the relevant range).
• Base case(s): verify the smallest value(s) directly; sometimes the first two or three are needed.
• When strong is needed: when proving P(k+1) requires P(j) for some j strictly less than k.
• Weak vs strong: "strong" refers to the stronger assumption, not a stronger conclusion. The strong form is often far more natural to use.

How It Works

Run the strong induction template:

1. Check the base case(s) by direct verification.
2. Assume P(j) holds for all j from the base up to k.
3. Prove P(k+1), freely using any of P(1) through P(k), especially the non-consecutive ones.
4. Conclude P(n) holds for all n in the range.

The key move is reducing the k+1 case to strictly smaller cases, then invoking the hypothesis on those.

Worked Example

Prove every integer n ≥ 2 can be written as a product of primes.

• Base case: n = 2 is prime, hence a product of primes.
• Strong hypothesis: assume every integer j with 2 ≤ j ≤ k factors into primes.
• Step: consider k+1. If prime, done. If composite, k+1 = a·b with 2 ≤ a, b ≤ k. By the hypothesis, a and b each factor into primes, and multiplying gives a factorization of k+1.
• Thus P(k+1) holds, and by strong induction every integer n ≥ 2 factors into primes.

Check: 12 = 3 × 4 = 3 × 2 × 2, using the hypothesis at j = 3 and j = 4, far below k: exactly the reach weak induction lacks.

Common Misconceptions

• "Strong induction proves stronger theorems." The name describes the hypothesis, not the power. Every strong-induction proof can be mechanically converted to weak induction. Use strong induction because it fits the problem, not because it proves more.
• "You can skip the base case." The hypothesis is empty below the base. Without a verified starting point the chain floats on nothing.
• "Strong induction is only for number theory." It appears in algorithm analysis (recurrences like T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + n), game theory and combinatorics wherever a problem splits into strictly smaller subproblems.

Real-World Applications

• Prime factorization: the fundamental theorem of arithmetic (existence half) is the textbook strong-induction proof.
• Recursive algorithms: correctness of divide-and-conquer algorithms like merge sort is proved by strong induction on input size.
• Structural induction: proofs about trees, formulas and other recursively built objects are strong induction in disguise.

Strong induction assumes P(1) through P(k) to prove P(k+1), handling statements whose k+1 case depends on much smaller cases. Reach for it whenever a problem breaks into strictly smaller subproblems.