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.
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
Worked example
- To prove every integer
n ≥ 2factors into primes, assume every integer from2throughnhas 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 it
- The next case depends on several earlier cases.
- You break
n + 1into smaller pieces. - The prompt mentions factorization, tilings, or recurrences.
Next recommended lesson
Try Least You Need to Know: Induction Basics next for a nearby refresher.
Least You Need to Know: Induction BasicsRelated lessons
Keep going with nearby lessons in the same topic.