4.7 Proof by induction

This technique can be useful when proving statements involving natural numbers or an ordered list of objects. To help gain an intuition about proof by induction, we use an analogy. Imagine an infinitely long line of dominoes, one for each natural number.

Proof by induction has two important parts.

1.

First, we concentrate only on the first domino in the line and topple it without thinking about what happens to any of the others.
2.

Second, we ensure that toppling any one domino will cause the next one to topple.

If both these conditions hold then we can conclude that all of the dominoes will topple. Toppling the first domino topples the second, which topples the third, which topples the fourth, and so on.

Now let’s see how this analogy translates to proving mathematical statements by discussing an example.

Example 4.31.

Let $n$ be a positive integer. We shall prove that $n^{2}+n$ is even by induction. (Note that this is a weaker result than the one in Exercise 4.12.) First we give each statement we would like to prove a label.

$P(n)$ :

$n^{2}+n$ is even.

This means, for example,

$P(1)$ :

$1^{2}+1$ is even;
$P(2)$ :

$2^{2}+2$ is even; and
$P(1001)$ :

$(1001)^{2}+1001$ is even.

In the domino analogy, each of these statements is represented by a domino, and the $k$ th domino in the line represents the statement

$P(k)$ :

$k^{2}+k$ is even.

Knocking over the first domino represents proving the statement $P(1)$ , i.e. proving that $1^{2}+1$ is even. We can do this directly: $1^{2}+1=2$ , which is even and so $P(1)$ is true.

Ensuring that toppling one domino will cause the next one to topple represents proving the conditional statement: for any positive integer $k$ , $P(k)\Rightarrow P(k+1)$ . We can prove this statement just as we can any conditional statement: by assuming that, for some positive integer $k$ , $P(k)$ is true and then deducing that $P(k+1)$ must also be true.

Assume, for some positive integer $k$ , that $P(k)$ is true, i.e. $k^{2}+k$ is even. Then, applying the definition, we can write $k^{2}+k=2l$ for some integer $l$ . To prove that $P(k+1)$ is true, i.e. that $(k+1)^{2}+(k+1)$ is even, we consider:

$\displaystyle(k+1)^{2}+(k+1)$	$\displaystyle=k^{2}+2k+1+k+1$	(expanding)
	$\displaystyle=(k^{2}+k)+2k+2$	(rearranging terms)
	$\displaystyle=2l+2k+2$	(replacing $k^{2}+k$ with $2l$ )
	$\displaystyle=2(l+k+1)$	(factorising).

Since $k$ and $l$ are integers, so is $(l+k+1)$ and so $(k+1)^{2}+(k+1)$ is even.

We have shown that $P(1)$ is true and proved that, for that for any positive integer $k$ , $P(k)\Rightarrow P(k+1)$ . Thus $P(n)$ is true for all positive integers $n$ by induction.

In general, to prove a statement $P(n)$ for all positive integers $n$ by induction:

1.

Prove that $P(1)$ is true; this is known as proving the base case.
2.

Prove that, for a positive integer $k$ , if $P(k)$ is true then $P(k+1)$ is true; this is known as the induction step.
3.

Conclude that $P(n)$ is true for all positive integers $n$ by induction.

Exercise 4.32.

Prove that, for any positive integer $n$ , $7^{n}-1$ is a multiple of $6$ .

Solution.First prove the base case $P(1)$ , i.e. that $7^{1}-1$ is a multiple of $6$ . This is true since $7^{1}-1=6$ , which is certainly a multiple of $6$ .

For the induction step, assume that $P(k)$ is true, i.e. that $7^{k}-1$ is a multiple of $6$ . We use this to prove that $P(k+1)$ is true, i.e. that $7^{k+1}-1$ is a multiple of $6$ . Write $7^{k}-1=6m$ , for some integer $m$ . Then $7^{k}=6m+1$ . Now

$\displaystyle 7^{k+1}-1$	$\displaystyle=7\times 7^{k}-1$	(since $7\times 7^{k}=7^{k+1}$ )
	$\displaystyle=7\times(6m+1)-1$	(since $7^{k}=6m+1$ )
	$\displaystyle=42m+6$	(expanding and gathering terms)
	$\displaystyle=6(7m+1)$	(factorising).

Because $7m+1$ is an integer, we have shown that $7^{k+1}-1$ is a multiple of $6$ .

Hence, for all positive integers $n$ , $7^{n}-1$ is a multiple of $6$ by induction.

You will meet slightly more sophisticated techniques based on proof by induction in your studies. But understanding the principle through the analogy and examples above will prepare you well.