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\). ”