Discrete Math › Section E · Sequences › Topic E.6
Strong induction
Ordinary induction lets each case lean on the one just before it. Strong induction lets it lean on every earlier case at once, which is exactly what you need when a problem breaks into smaller pieces of unpredictable size.
In this topic
- When one step back is not enough
- The principle of strong induction
- Worked example: every integer factors into primes
- Worked example: postage stamps
- How many base cases?
- Worked example: confirming a closed formula
- Worked example: sums of powers of 2
- Divide and conquer
- Is strong induction really stronger?
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…