Proof by mathematical induction

What you’ll learn

• Write a complete base, hypothesis and induction step.
• Apply induction to sums, recurrences, divisibility and matrix powers.

Understand the idea

Induction proves infinitely many statements through a starting case and a chain of implications. First establish the statement at the initial integer. Then assume it is true at an arbitrary integer $k$ and use that assumption to prove the case $k+1$.

For a sum, add the next term to the assumed formula. For divisibility, rewrite the next expression as a multiple of the assumed one plus a known multiple of the divisor. For a recurrence or matrix power, apply one further recurrence step or matrix multiplication. End by stating the valid integer range.

Key formulae

$$P(1),\quad P(k)\Rightarrow P(k+1)\quad\Longrightarrow\quad P(n)\text{ for every }n\ge1$$

$$S_{k+1}=S_k+u_{k+1}$$

$$A^{k+1}=A^kA$$

Worked example

Prove $1+3+\cdots+(2n-1)=n^2$ for all positive integers $n$.

1. At $n=1$, both sides equal $1$.
2. Assume $S_k=k^2$ for some positive integer $k$.
3. Then $S_{k+1}=k^2+(2k+1)=(k+1)^2$.
4. The statement holds at $1$ and passes from $k$ to $k+1$, so it holds for all positive integers.

Answer: $\sum_{r=1}^n(2r-1)=n^2$, proved by induction.