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 | _r=1k+1u_r= _r=1ku_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=f(n), the target is S_k+1=f(k+1). After using S_k+1=S_k+u_k+1 and the hypothesis S_k=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+. s+n, write the first two lines of the k+1 case and identify the precise moment when S_k may be replaced.