# A calculus of the absurd

#### 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

\begin{equation} 2^{n+1} + 5\cdot 9^{n} \end{equation}

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

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.

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

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.

\begin{align} & P(k)=2^{k+1} + 5\cdot 9^{k} \\ & 2^{k+1} = P(k) - 5\cdot 9^{k} \end{align}

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

\begin{align} P(k+1) &= 2^{k+1+1} + 5\cdot 9^{k+1} \\ &= 2\cdot 2^{k+1} + 5\cdot 9^{k+1} \\ &= 2\left (P(k) - 5\cdot 9^{k}\right ) + 5\cdot 9^{k+1} \end{align}

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

\begin{align} P(k+1) &= 2\left (P(k) - 5\cdot 9^{k}\right ) + 5\cdot 9^{k+1} \\ &= 2P(k) - 10\cdot 9^{k} + 5\cdot 9^{k+1} \\ &= 2P(k) - 10\cdot 9^{k} + 5\cdot 9\cdot 9^{k} \\ &= 2P(k) + 35\cdot 9^{k} \end{align}

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: “ 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$$. ”