Induction / Strong Induction
Least You Need to Know: Strong Induction
Strong induction assumes the claim holds for **all earlier cases up to n** and then proves it for `n + 1`.
The least you need to know
- Strong induction assumes all previous cases, not just one case.
- The inductive step still proves a new case from earlier ones.
- You need the correct base cases for the recurrence or decomposition you use.
- Strong and ordinary induction are both valid proof methods.
- Use strong induction when the next case depends on several earlier cases.
Key notation
P(n)
statement for integer n
∀k ≤ n
for all earlier cases up to n
n + 1
next case
Tiny worked example
- To prove every integer `n ≥ 2` factors into primes, assume every integer from `2` through `n` has a prime factorization.
- For `n + 1`, either it is prime or it factors into smaller integers.
- The smaller factors already have prime factorizations by the strong induction hypothesis.
Common mistakes
- Students often state only `P(n)` instead of all earlier cases.
- Students sometimes forget extra base cases needed by a recurrence.
- Students may use strong induction when the proof still needs an ordinary induction structure.
How to recognize this kind of problem
- The next case depends on several earlier cases.
- You break `n + 1` into smaller pieces.
- The prompt mentions factorization, tilings, or recurrences.