Building the Next Case
Building the Next Case
The algebraic heart of induction is to rewrite the \(k+1\) case until the \(k\) case becomes visible. Only then may the induction hypothesis be substituted.
| Structure | Start the \(k+1\) case with | Where \(P(k)\) appears |
|---|---|---|
| Sum | \(\displaystyle\sum\limits_{r=1}^{k+1}u_r=\sum\limits_{r=1}^{k}u_r+u_{k+1}\) | The first \(k\) terms |
| Recurrence | Write the given rule for \(u_{k+1}\). | The occurrence of \(u_k\) |
| Divisibility | Rewrite the new expression using the old expression plus a visible multiple of the divisor. | A factor known to be divisible |
- Write the exact target right-hand side for \(P(k+1)\).
- Start from the left-hand side of \(P(k+1)\), not from the desired right-hand side.
- Split off the new term.
- Substitute the induction hypothesis once the \(k\) case is visible.
- Factorise until the expression matches the target exactly.
For a sum formula \(S_n=\mathrm{f}(n)\), the target is \(S_{k+1}=\mathrm{f}(k+1)\). After using \(S_{k+1}=S_k+u_{k+1}\) and the hypothesis \(S_k=\mathrm{f}(k)\), all remaining work is ordinary algebra.
Do not replace every \(k\) by \(k+1\) in the induction hypothesis. The hypothesis is known only at \(k\); the proof must build the next case.
If \(S_n=1+2+\cdots+n\), write the first two lines of the \(k+1\) case and identify the precise moment when \(S_k\) may be replaced.
Let \(d\) be a positive integer. Write the induction hypothesis as \(E_k=dm\) for some integer \(m\). If the next expression is \(E_{k+1}=aE_k+db\), with integers \(a,b\), then \(E_{k+1}=d(am+b)\), so the next case is also divisible by \(d\).
To prove that \(7^n-1\) is divisible by \(6\) for every positive integer \(n\).
For \(n=1\), \(7^1-1=6\), so the base case holds.
Assume that \(7^k-1=6m\) for an integer \(m\). Then
\(7^{k+1}-1\)\({}=7(7^k-1)+6\)\({}=7(6m)+6\)\({}=6(7m+1).\)
Since \(7m+1\) is an integer, the induction step follows. The base case and step establish the claim for all positive integers \(n\).
Create a free account to practise similar questions.
Need help? Join our JC Math tuition classes.
Learn more