Session 5B
Induction with divisibility
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
- Induction is especially clean for divisibility statements because many expressions have a natural recurrence. Suppose you want to prove something like "7^n - 1 is divisible by 6 for all n >= 1." The inductive step works because 7^(k+1) - 1 can be rewritten as 7(7^k - 1) + 6. That splits the expression into a multiple of the previous term plus an obvious multiple of 6. This is the general pattern: rewrite the (k+1) expression so it contains the k expression plus a term you can directly show is divisible by the target integer.
- The "rewrite to reveal the hypothesis" habit is the core skill. If your hypothesis is "6 | (7^k - 1)," you want to manufacture (7^k - 1) somewhere in the next expression. Similarly, induction can prove inequalities, sums, and recursion formulas, but divisibility is where you see the mechanism most transparently because "being divisible by m" is stable under adding multiples of m.
Practice
- 1Prove: 7^n - 1 is divisible by 6 for n >= 1.
- 2Prove: 3 divides (n^3 - n) for all integers n.
Show answers / outlines
Answers
- 17^(k+1) - 1 = 7(7^k - 1) + 6.
- 2Factor n(n - 1)(n + 1).
MCQ
A good inductive step for 7^n - 1 divisible by 6 starts with: