The principle of mathematical induction

In the chap­ter on pro­gres­sions we found for­mu­las such as $1 + 3 + 5 + \cdots + (2n - 1) = n^2$. You can check them for $n = 1, 2, 3$ and as many more val­ues as you like, but a for­mula is meant to hold for every nat­ural num­ber, and nobody can check infi­nitely many cases. Math­e­mat­i­cal induc­tion is the method that closes this gap. It proves a state­ment for all nat­ural num­bers with just two short argu­ments.

Why check­ing cases is not enough#

Look at the expres­sion $n^2 + n + 41$.

Every one of these is a prime num­ber. In fact the value is prime for every $n$ from 1 to 39. It would be very tempt­ing to say "$n^2 + n + 41$ is always prime". But for $n = 40$:

$$40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41 \times 41$$

which is not prime. Thirty-nine suc­cess­ful checks proved noth­ing. A pat­tern sug­gests what might be true; only a proof shows that it is true.

State­ments about n#

A state­ment that depends on a nat­ural num­ber $n$ is writ­ten $P(n)$. For exam­ple, let $P(n)$ be the state­ment

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

Then $P(1)$ says $1 = 1^2$, $P(2)$ says $1 + 3 = 2^2$, $P(3)$ says $1 + 3 + 5 = 3^2$, and so on. Each $P(n)$ is a sin­gle state­ment that is either true or false. Our aim is to show that every one of them is true.

The domi­noes#

Imag­ine an end­less row of domi­noes stand­ing on end. Sup­pose you know two things:

1. The first domino falls.
2. When­ever any domino falls, it knocks over the next one.

Then every domino falls. The first one falls by fact 1; it knocks over the sec­ond by fact 2; the sec­ond knocks over the third; and so on with­out end. No domino can be left stand­ing.

The prin­ci­ple of math­e­mat­i­cal induc­tion#

Let $P(n)$ be a state­ment about nat­ural num­bers. If

1. (Base step) $P(1)$ is true, and
2. (Induc­tive step) for every nat­ural num­ber $k$, if $P(k)$ is true then $P(k + 1)$ is true,

then $P(n)$ is true for every nat­ural num­ber $n$.

In the induc­tive step we do not claim that $P(k)$ is true. We assume it, only for the sake of the argu­ment, and show that $P(k + 1)$ would fol­low. This assump­tion is called the induc­tion hypoth­e­sis. It is exactly fact 2 about the domi­noes: "if this one falls, the next one falls".

How to set out a proof#

Every induc­tion proof has the same four parts:

1. Base step: check that $P(1)$ is true.
2. Induc­tion hypoth­e­sis: assume $P(k)$ is true for some nat­ural num­ber $k$. Write out what this says.
3. Induc­tive step: using the hypoth­e­sis, prove $P(k + 1)$. Write out what $P(k + 1)$ says first, so you know where you are head­ing.
4. Con­clu­sion: by the prin­ci­ple of math­e­mat­i­cal induc­tion, $P(n)$ is true for all nat­ural num­bers $n$.

Exam­ple 1#

Prove that $1 + 3 + 5 + \cdots + (2n - 1) = n^2$ for every nat­ural num­ber $n$.

Let $P(n)$ be the state­ment $1 + 3 + 5 + \cdots + (2n - 1) = n^2$.

Base step. For $n = 1$, the left side is just the first term, 1, and the right side is $1^2 = 1$. So $P(1)$ is true.

Induc­tion hypoth­e­sis. Assume $P(k)$ is true:

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

Induc­tive step. We must prove $P(k + 1)$, which says

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

(The $(k + 1)$th odd num­ber is $2(k + 1) - 1 = 2k + 1$.) The left side is the sum of the first $k$ odd num­bers plus one more term. By the hypoth­e­sis the first $k$ terms add up to $k^2$, so

$$\text{LHS} = k^2 + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2 = \text{RHS}$$

So $P(k + 1)$ is true when­ever $P(k)$ is true.

Con­clu­sion. By the prin­ci­ple of math­e­mat­i­cal induc­tion, the state­ment is true for every nat­ural num­ber $n$.

Exam­ple 2#

Prove that $2 + 4 + 6 + \cdots + 2n = n(n + 1)$ for every nat­ural num­ber $n$.

Base step. For $n = 1$: LHS $= 2$, RHS $= 1 \times 2 = 2$. True.

Induc­tion hypoth­e­sis. Assume $2 + 4 + \cdots + 2k = k(k + 1)$.

Induc­tive step. We must show $2 + 4 + \cdots + 2k + 2(k + 1) = (k + 1)(k + 2)$. Using the hypoth­e­sis,

$$\text{LHS} = k(k + 1) + 2(k + 1) = (k + 1)(k + 2) = \text{RHS}$$

Tak­ing out the com­mon fac­tor $(k + 1)$ is a step you will use again and again.

Con­clu­sion. By induc­tion, the result holds for all nat­ural num­bers $n$.

Both steps are needed#

Leav­ing out either step can "prove" some­thing false.

With­out the base step. Let $P(n)$ be "$n^2 + n$ is odd". Sup­pose $k^2 + k$ is odd. Then

$$(k + 1)^2 + (k + 1) = k^2 + k + 2(k + 1)$$

which is an odd num­ber plus an even num­ber, so odd. The induc­tive step works. But $P(1)$ says $1 + 1 = 2$ is odd, which is false. In fact $n^2 + n = n(n + 1)$ is always even, because one of two con­sec­u­tive num­bers is even. The domi­noes would all fall if the first fell, but the first never falls.

With­out the induc­tive step. For $n^2 + n + 41$ the base step works (43 is prime), and so do the next 38 cases, but there is no argu­ment that each case leads to the next, and the state­ment fails at $n = 40$.

Prac­tice#

1. Write out the state­ments $P(1)$, $P(2)$ and $P(3)$ for $P(n)$: $\displaystyle 1 + 2 + \cdots + n = \frac{n(n + 1)}{2}$, and check that each is true.
2. Find the value of $n^2 + n + 41$ when $n = 41$. Is it prime?
3. In a proof of $\displaystyle 5 + 10 + \cdots + 5n = \frac{5n(n + 1)}{2}$, write out exactly what $P(k + 1)$ says.
4. Prove by induc­tion that $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}$.
5. Prove by induc­tion that $\displaystyle 5 + 10 + 15 + \cdots + 5n = \frac{5n(n + 1)}{2}$.
6. Prove by induc­tion that $1 + 5 + 9 + \cdots + (4n - 3) = n(2n - 1)$.
7. Prove by induc­tion that $3 + 7 + 11 + \cdots + (4n - 1) = n(2n + 1)$.
8. Let $P(n)$ be "$n^2 - n + 1$ is even". Show that if $P(k)$ is true then $P(k + 1)$ is true. Is $P(n)$ true for all $n$? Explain.

Answers#