Session 5D
Induction pitfalls and polishing
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
- Most induction errors are structural, not algebraic. A frequent mistake is a weak base case, where you prove n = 1 but your inductive step actually needs n = 2 and n = 3 as well. Another common mistake is circularity, where you "prove" the k+1 case by rewriting it into itself without progress. Good induction proofs explicitly label the hypothesis, explicitly show where it is used, and clearly finish with the exact k+1 statement, not something close to it.
- Polishing an induction proof means making the logic easy to audit. A clean inductive step often starts with the left-hand side of the k+1 statement, then performs algebra until the k-case statement appears, then replaces it using the inductive hypothesis, then simplifies to reach the desired form. If you can't find where to use the hypothesis, that's a sign you need a different algebraic rewrite or a different proof method. Induction is a tool, not a default. Use it when the statement naturally relates n to n+1.
Practice
Rewrite one induction proof you wrote this week.
Week quiz
- 1Induction: Prove 1 + 2 + ... + n <= n^2 for n >= 1.
Show quiz answers
Quiz answers
- 1Use induction; check base n = 1, then add k + 1.
MCQ
Which is a common induction mistake?