Key Takeaways: Mathematical Induction
A one-page reference card. Reread it before an exam or before writing your next induction proof.
The technique at a glance
Mathematical induction proves $P(n)$ for all integers $n \ge \text{start}$ using two finite steps.
| Part | What you write | Why it's there |
|---|---|---|
| State $P(n)$ | "Let $P(n)$ be the statement that …" | Pins down exactly what you're proving |
| Base case | Prove $P(\text{start})$ directly | Push the first domino |
| Inductive step | Fix arbitrary $k \ge \text{start}$; assume $P(k)$; prove $P(k+1)$ | Each domino topples the next |
| Conclude | "By induction, $P(n)$ holds for all $n \ge \text{start}$. $\blacksquare$" | Chains the dominoes to infinity |
The assumption $P(k)$ is the inductive hypothesis. You prove an implication — assuming $P(k)$ to get $P(k+1)$ is not circular.
Recursion ↔ induction (the same shape)
| Induction proof | Recursive program |
|---|---|
| Base case $P(\text{start})$ | Non-recursive (terminating) branch |
| Inductive hypothesis $P(k)$ | "the recursive call returns the right answer" |
| Inductive step | Combine the recursive result correctly |
| Conclusion: correct for all $n$ | Function correct for all inputs |
Iterative code uses a loop invariant: initialization = base case, maintenance = inductive step, plus a termination argument.
Proof engines (memorize these moves)
- Summation induction: peel off the last term, then apply the hypothesis. $$\sum_{i=1}^{k+1} a_i = \left(\sum_{i=1}^{k} a_i\right) + a_{k+1} \xrightarrow{\text{hyp.}} (\text{closed form at }k) + a_{k+1}.$$
- Divisibility induction: unpack "$d \mid x$" as "$x = d m$", do algebra, repackage as "$d \mid (\dots)$".
- Inequality induction: bound $f(k+1)$ using $f(k)$ (the hypothesis), then close the remaining gap.
Quick-reference results proven this chapter
| Identity | Holds for |
|---|---|
| $\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$ | $n \ge 1$ |
| $\sum_{i=1}^{n} (2i-1) = n^2$ | $n \ge 1$ |
| $2^n > n^2$ | $n \ge 5$ (note the base case!) |
| $3 \mid (4^n - 1)$ | $n \ge 0$ |
| $\sum_{i=1}^{n} F_i = F_{n+2} - 1$ | $n \ge 1$ |
When to reach for induction
Is the claim "for all integers n >= something"?
├─ No → induction is probably the wrong tool.
└─ Yes → Does P(k+1) naturally build on P(k)?
├─ Yes, on the single previous case → ordinary induction (this chapter)
├─ Yes, but needs several previous cases → STRONG induction (Chapter 7)
└─ It's about a recursively-built object → STRUCTURAL induction (Chapter 7)
Common pitfalls
- Wrong base case. Test small $n$ first; start where the claim becomes true ($2^n > n^2$ starts at 5).
- Step that secretly needs large $k$. The inductive step must hold for every $k \ge \text{start}$. The "all horses same color" fallacy breaks because its overlap argument fails at $k=1$.
- Skipped/false base case. A valid step with no valid base proves nothing.
- Needing two cases back. If you must assume $P(k-1)$ and $P(k)$, you need strong induction.
Toolkit addition
recurrences.py: check_identity(lhs, rhs, upto, start) (tests a conjectured identity, returns the
first counterexample or None) and a naive fib(n). Remember: a test that finds no counterexample is
evidence, not a proof.