In precalculus you used proof by induction to prove formulas for sums. Induction proves much more: divisibility facts, inequalities, statements about all sizes of objects. The structure stays the same; what changes is the inductive step, which becomes a small direct proof in which the case $n = k$ must actually be used.
Key idea
To prove $P(n)$ for every integer $n \ge n_{0}$: (1) base case, prove $P(n_{0})$; (2) inductive step, assume $P(k)$ for some $k \ge n_{0}$ (the inductive hypothesis) and prove $P(k + 1)$. The step works by rewriting the case $k + 1$ so that the case $k$ appears inside it.
Why it works
The base case knocks over the first domino, and the step guarantees each domino knocks over the next: $P(n_{0})$ gives $P(n_{0} + 1)$, which gives $P(n_{0} + 2)$, and so on forever. Two things can go wrong. If the step never uses $P(k)$, it is really a direct proof in disguise or, more often, it has a gap. And if the base case is checked where the claim is false, nothing gets started; an inequality like $2^{n} > n^{2}$ must start where it really begins to hold.
| $n$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|---|
| $2^{n}$ | $2$ | $4$ | $8$ | $16$ | $32$ | $64$ | $128$ |
| $n^{2}$ | $1$ | $4$ | $9$ | $16$ | $25$ | $36$ | $49$ |
| $2^{n} > n^{2}$? | yes | no | no | no | yes | yes | yes |
Worked examples
Worked example: A divisibility proof
Prove that $3 \mid 4^{n} - 1$ for every integer $n \ge 1$.
- Base case $n = 1$: $4 - 1 = 3$, which is divisible by $3$.
- Inductive step: assume $3 \mid 4^{k} - 1$, say $4^{k} - 1 = 3m$.
- Rewrite the next case to contain the old one: $4^{k+1} - 1 = 4 \cdot 4^{k} - 1 = 4(4^{k} - 1) + 3$.
- Substitute: $4(3m) + 3 = 3(4m + 1)$, a multiple of $3$. So the claim holds for every $n \ge 1$.
Answer: $4^{k+1} - 1 = 4(4^{k} - 1) + 3 = 3(4m + 1)$
Worked example: An inequality with a late start
Prove that $2^{n} > n^{2}$ for every integer $n \ge 5$.
- Base case $n = 5$: $32 > 25$. (The table shows why we cannot start lower: it fails at $2$, $3$ and $4$.)
- Step: assume $2^{k} > k^{2}$ with $k \ge 5$. Then $2^{k+1} = 2 \cdot 2^{k} > 2k^{2}$.
- It remains to show $2k^{2} \ge (k + 1)^{2}$, that is, $k^{2} \ge 2k + 1$, or $(k - 1)^{2} \ge 2$. That holds for every $k \ge 3$, so certainly for $k \ge 5$.
- Together: $2^{k+1} > 2k^{2} \ge (k + 1)^{2}$.
Answer: Base $n = 5$; step $2^{k+1} > 2k^{2} \ge (k + 1)^{2}$.
Worked example: Factorials outgrow powers
Prove that $n! > 2^{n}$ for every integer $n \ge 4$.
- Base case $n = 4$: $24 > 16$.
- Step: assume $k! > 2^{k}$ with $k \ge 4$. Then $(k + 1)! = (k + 1) \cdot k! > (k + 1) \cdot 2^{k}$.
- Since $k + 1 \ge 5 > 2$, this is more than $2 \cdot 2^{k} = 2^{k+1}$.
Answer: $(k + 1)! > (k + 1)2^{k} > 2^{k+1}$
Common mistake
Starting at the wrong base case, or never using $P(k)$. A "proof" of $2^{n} > n^{2}$ that checks $n = 1$ and then runs the step has a hidden flaw: the step needed $k \ge 3$, and the claim is false at $n = 2, 3, 4$. And a step that proves $P(k + 1)$ from scratch, without the hypothesis, has usually skipped something. Check: test the claim at the first few values to find where it truly starts, and point to the line of the step where $P(k)$ is used.