6.3 Proof by induction

Definition 6.3.1

The principle of mathematical induction states that if we have a statement which depends on a natural number $n$ and

•

if the statement is true for $n=s$ ( $s$ is some natural number, usually $0$ or $1$ )
•

and for every natural number $k\geqq s$ if the statement is true for $n=k$ , then the statement must also be true for $n=k+1$

then the statement is true for every $n\geqq s$ .

One way of thinking about induction is by considering an analogy to dominoes. If we have a row of dominoes, and we knock one domino over, and knocking any given domino over means that the next one over, then all the dominoes will fall over.

A general formula for solving any induction problem involving property $P(n)$ reads something like:

•

The basis step - show that $P(a)$ is true.
•

The inductive step - show that if $P(k)$ is true, then this implies that $P(k+1)$ is also true.
•

The completion step - write some words stating that as $P(a)$ is true and $P(k)$ being true implies $P(k+1)$ is true, $P(n)$ must be true for all integer $n$ with $n\geqq a$ .

It probably helps to include some examples (see the next sections).

6.3.1 Divisibility

Example 6.3.1

Let the function $f(x)$ be defined by

2^{n+1}+5\cdot 9^{n}

(6.3)

Show that for all $n\in\mathbb{N_{0}}$ , $f(n)$ is divisible by 7.

The first step is the basis case. By calculation $f(1)=2^{2}+5\cdot 9=49$ (which is divisible by $7$ , as $7\cdot 7=49$ ).

The next step is the inductive step. Here we assume that $f(k)$ is divisible by $7$ , and then consider $P(k+1)$ .

³³ 3 People wiser than me have suggested that a clever ”trick” we can pull here is to show that the difference between

P(k+1)

and

P(k)

is divisible by

7

(which implies that

P(k)

being divisible implies that

P(k+1)

is also divisible). I’ve never found it particularly helpful.

f(k+1)=2^{k+1+1}+5\cdot 9^{k+1}

(6.4)

The key thing here is to apply the inductive hypothesis (aka the fact that we have assumed that $f(k)$ is divisible by $7$ ). This is pretty much always the first thing to do!

We know that $f(k)=2^{k+1}+5\cdot 9^{k}$ . Currently, this doesn’t help very much as we have no way to apply it to the equation above. What we can do, however, is rearrange it to express either $2^{k+1}$ or $5\cdot 9^{k}$ in terms of $P(k)$ and the other term. In this case, we’ll choose to eliminate $2^{k+1}$ , but we could do it the other way, and it would be fine.

	$\displaystyle P(k)=2^{k+1}+5\cdot 9^{k}$		(6.5)
	$\displaystyle 2^{k+1}=P(k)-5\cdot 9^{k}$		(6.6)

We can now apply this to $P(k+1)$ , by taking out a factor of $2$ from $2^{k+1+1}$ and then substituting.

$\displaystyle P(k+1)$	$\displaystyle=2^{k+1+1}+5\cdot 9^{k+1}$	(6.7)
	$\displaystyle=2\cdot 2^{k+1}+5\cdot 9^{k+1}$	(6.8)
	$\displaystyle=2\left(P(k)-5\cdot 9^{k}\right)+5\cdot 9^{k+1}$	(6.9)

Now we can factorise the expression, and hopefully find a factor of $7$ lurking somewhere!

$\displaystyle P(k+1)$	$\displaystyle=2\left(P(k)-5\cdot 9^{k}\right)+5\cdot 9^{k+1}$	(6.10)
	$\displaystyle=2P(k)-10\cdot 9^{k}+5\cdot 9^{k+1}$	(6.11)
	$\displaystyle=2P(k)-10\cdot 9^{k}+5\cdot 9\cdot 9^{k}$	(6.12)
	$\displaystyle=2P(k)+35\cdot 9^{k}$	(6.13)

This means that $P(k)$ being divisible by $7$ implies that $P(k+1)$ is also divisible by $7$ .

Now onto the completion step! This is pretty much the same every time: \say Thus $P(n)$ implies $P(n+1)$ and as $P(1)$ is true, $P(n)$ holds for all $n\in\mathbb{N}$ where $n\geqq 1$ .

6.3.2 From $k$ to $k+1$

Sometimes it can be more practical to work from the case $n=k$ and apply operations to that to form the case $n=k+1$ , rather than trying to expose $n=k$ within $n=k+1$ (i.e. write the case $n=k+1$ in terms of $n=k$ ).

TODO: example

6.3 Proof by induction

Definition 6.3.1

6.3.1 Divisibility

Example 6.3.1

6.3.2 From kk to k+1k+1

6.3.2 From $k$ to $k+1$