Strong Induction
What You'll Learn
You'll learn a more powerful version of mathematical induction that lets you assume the truth of all earlier cases, not just the immediately preceding one.
The Core Idea
In regular induction (which you've learned), your inductive hypothesis assumes that a statement is true for some value k, then you prove it for k + 1. You're only looking one step back.
Strong induction gives you more to work with: you assume the statement is true for all values from the base case up through k, then prove it for k + 1. It's like having access to the entire history of true cases, not just the most recent one.
Structure of a Strong Induction Proof
- Base Case: Prove the statement for one or more initial values (just like before)
- Inductive Hypothesis: Assume the statement is true for all values from the base case up to some arbitrary k
- Inductive Step: Use any or all of those assumed cases to prove the statement for k + 1
When Is This Useful?
Strong induction shines when proving something for k + 1 requires looking back more than one step. For example:
- Proving properties of the Fibonacci sequence (where
F(n) = F(n-1) + F(n-2)depends on two previous terms) - Showing every integer ≥ 2 can be factored into primes
- Analyzing algorithms with divide-and-conquer recurrences
Analogy
Regular induction is like climbing a ladder where each rung only depends on the one directly below it. Strong induction is like climbing where you can use any lower rung for support—much more flexible!
Key Takeaway: Strong induction assumes truth for all prior cases up to k, giving you a richer hypothesis to prove the next case—essential when problems naturally depend on multiple earlier values.