Review: Ordinary vs. Strong Induction
You'll learn: How ordinary and strong induction differ, and when each proof technique is most appropriate.
The Core Difference
Both ordinary induction and strong induction prove statements for all integers n ≥ some base case. The key difference lies in what you assume during the inductive step:
- Ordinary Induction: Assume P(k) is true, then prove P(k+1)
- Strong Induction: Assume P(1), P(2), ..., P(k) are all true, then prove P(k+1)
Think of it like climbing a ladder. Ordinary induction says "if I can stand on rung k, I can reach rung k+1." Strong induction says "if I've successfully climbed all rungs up to k, I can reach rung k+1."
When Is Strong Induction Needed?
Strong induction becomes essential when proving P(k+1) requires information from multiple earlier cases, not just the immediately preceding one.
Classic example: Proving the Fundamental Theorem of Arithmetic (every integer > 1 has a unique prime factorization). To show n has a prime factorization, you might write n = a·b where both a and b are smaller than n. You need to assume factorizations exist for both a and b—not just n-1.
Similarly, recursively defined sequences like the Fibonacci sequence (where F(n) = F(n-1) + F(n-2)) naturally require strong induction because computing the nth term depends on two previous terms.
Are They Really Different?
Logically, strong induction and ordinary induction are equivalent—anything provable with one is provable with the other. However, strong induction often makes proofs cleaner and more natural when dealing with recursive structures or problems where the (k+1)th case builds on multiple previous cases.
Key Takeaway: Use ordinary induction when P(k+1) depends only on P(k); use strong induction when P(k+1) may depend on several (or all) earlier cases P(1) through P(k).