# 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)$.

33 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