Session 5C
Strong induction
45-75 min - work through lesson notes, practice, and the MCQ check.
In progress
Account sync
Sign in to keep this session synced across devices.
Account sync disabled
Add Supabase environment variables to enable account sync. Progress is saved locally in this browser for now.
Session tips
- Finish the MCQ before marking complete.
- Check the answer outlines after trying on paper.
- Mark complete to update your certificate progress.
Lesson notes
- Strong induction is a variation where, to prove the statement for k+1, you may assume it is true for all values up to k, not just for k alone. This is useful when k+1 depends on multiple earlier cases. For example, proving "every integer n >= 2 can be written as a product of primes" uses strong induction. In the inductive step, either n is prime (done) or n is composite, meaning n = ab with 2 <= a,b < n. Then you need the statement for a and b, which are smaller than n, not necessarily equal to n-1. Strong induction gives you that.
- Conceptually, strong induction is not "stronger" than normal induction in logical power, but it is stronger in convenience. It matches many natural recursive breakdowns, like factoring, tiling problems, and coin problems. The key requirement is still the same: you must cover the base cases that make the argument work. If your breakdown uses n-4 or n-5, you must ensure those earlier statements exist and have been established.
Practice
- 1Prove: Every integer n >= 2 can be written as a product of primes.
- 2Prove: Every amount of postage >= 12 can be made with 4 and 5 cent stamps.
MCQ
In strong induction, the hypothesis assumes: