Math 341

Proof by Induction

Mathematical Induction, or “induction” is a technique to prove a list of mathematical statements

$P_1, P_2, P_3, \dots, P_n, P_{n+1}, \dots,$

Here each $P_n$ stand for a mathematical statement. Example: $P_n$ could be the statement

• $P_n\quad$:$\quad$ “$1+2+3+\cdots+n = \frac12 n(n+1)$”

One way to prove that each $P_n$ is true is to try to prove them one by one

• prove $P_1$
• prove $P_2$
• prove $P_3$
• $\quad\vdots$
• prove $P_n$
• $\quad\vdots$

and so on. The idea of mathematical induction is that once you have proved $P_1$, $P_2$, …, $P_n$, you know that $P_1$, $P_2$, …, $P_n$ are true so you could use that knowledge when you try to prove $P_{n+1}$.

An induction proof then always consists of the following steps:

1. The initial case: a proof that $P_1$ is true
2. The induction step: assuming that $P_1, \dots, P_n$ are true, prove $P_{n+1}$ is true.

The example: prove $1+2+3+\cdots+n = \frac12 n(n+1)$ for all $n$

In the above example the initial step requires us to prove “$1+2+3+\cdots+n = \frac12 n(n+1)$” when $n=1$. For $n=1$ the statement is

$P_1:\quad 1 = \frac12 \cdot1\cdot(1+1)$

which is true, by direct calculation.

In the induction step we assume that

$P_n:\quad 1+2+3+\cdots+n = \frac12 n(n+1)$

is true, and we have to prove

$P_{n+1} : \quad 1+2+3+\cdots+n + (n+1) = \frac12 (n+1)\bigl((n+1)+1\bigr).$

This step requires some algebra:

$\begin{aligned} 1+2+3+\cdots+n + (n+1) &= \frac12 n(n+1) + (n+1) &\text{(use $P_n$)} \\ &= \left(\frac12 n+1\right)(n+1) &\text{(factor)}\\ &= \frac12 (n+2)(n+1)\\ &= \frac12 (n+1)\bigl((n+1)+1\bigr) \end{aligned}$

So we have shown $P_n\implies P_{n+1}$ for any $n\in \N$: this is called the induction step.

The induction step gives us the chain of implications

$P_1\implies P_2\implies P_3\implies P_4\implies \cdots$

and since we have checked that $P_1$ is true, it follows that all $P_n$ are true.