Mathematical Induction

Mathematical induction proves a statement for every integer in a specified range by linking a base case to an inductive step. It is especially useful for recursive definitions, sums, and statements about algorithms.

The induction principle

TheoremPrinciple of mathematical induction

Let $P(n)$ be a proposition for each integer $n\ge n_0$. If

1. $P(n_0)$ is true, and
2. for every $k\ge n_0$, $P(k)$ implies $P(k+1)$,

then $P(n)$ is true for every integer $n\ge n_0$.

The base case starts the chain. The inductive step shows that truth at one index propagates to the next. Both parts are necessary.

ExampleThe sum of the first integers

Prove that

$$1+2+\cdots+n=\frac{n(n+1)}{2}$$

for every integer $n\ge1$.

Proof

For $n=1$, both sides equal $1$.

Assume the identity holds for $n=k$. Then

$$\begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\\ &=\frac{(k+1)(k+2)}{2}. \end{aligned}$$

This is the required formula with $n=k+1$. Therefore the identity holds for all $n\ge1$.

Strong induction

In strong induction, the inductive hypothesis assumes $P(j)$ for every $j$ from $n_0$ through $k$, rather than only $P(k)$. If that collection of assumptions proves $P(k+1)$, the same induction principle applies.

TheoremStrong induction principle

Let $P(n)$ be a proposition for every integer $n\ge n_0$. If $P(n_0)$ is true and, for every $k\ge n_0$, the truth of all statements

$$P(n_0),P(n_0+1),\ldots,P(k)$$

implies $P(k+1)$, then $P(n)$ is true for every $n\ge n_0$.

Strong induction is useful when the next case depends on several earlier cases, as in recursive algorithms and factorisation arguments.

ExampleThe sum of the first odd numbers

For every integer $n\ge1$,

$$1+3+5+\cdots+(2n-1)=n^2.$$

Proof

The identity holds for $n=1$. If it holds for $n=k$, then

$$1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1=(k+1)^2.$$

The induction principle completes the proof.

A reusable proof template

When writing an inductive proof, state the starting index explicitly. Then separate the base case from the inductive hypothesis and the inductive step. In the step, first write the target expression for $k+1$, and only then invoke the hypothesis. This makes it easier to detect an unjustified change of index or a missing term.

ExerciseA sum of reciprocals

Prove that, for every integer $n\ge1$,

$$\sum_{i=1}^{n}\frac{1}{(2i-1)(2i+1)}=\frac{n}{2n+1}.$$

Solution

The base case is $1/3=1/(2\cdot1+1)$. Assuming the formula for $k$, the sum through $k+1$ is

$$\begin{aligned} \frac{k}{2k+1}+\frac{1}{(2k+1)(2k+3)} &=\frac{k(2k+3)+1}{(2k+1)(2k+3)}\\ &=\frac{(k+1)(2k+1)}{(2k+1)(2k+3)}\\ &=\frac{k+1}{2k+3}. \end{aligned}$$

This is the formula at $k+1$.

The source chapter contains additional exercises on sums and recurrence relations. They can be migrated in a later batch after their algebra has been checked individually.