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 nn and

  • if the statement is true for n=sn=s (ss is some natural number, usually 0 or 11)

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

then the statement is true for every nsn\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)P(n) reads something like:

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

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

  • The completion step - write some words stating that as P(a)P(a) is true and P(k)P(k) being true implies P(k+1)P(k+1) is true, P(n)P(n) must be true for all integer nn with nan\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)f(x) be defined by

2n+1+59n2^{n+1}+5\cdot 9^{n} (6.3)

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

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

The next step is the inductive step. Here we assume that f(k)f(k) is divisible by 77, and then consider P(k+1)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)P(k+1) and P(k)P(k) is divisible by 77 (which implies that P(k)P(k) being divisible implies that P(k+1)P(k+1) is also divisible). I’ve never found it particularly helpful.
f(k+1)=2k+1+1+59k+1f(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)f(k) is divisible by 77). This is pretty much always the first thing to do!

We know that f(k)=2k+1+59kf(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 2k+12^{k+1} or 59k5\cdot 9^{k} in terms of P(k)P(k) and the other term. In this case, we’ll choose to eliminate 2k+12^{k+1}, but we could do it the other way, and it would be fine.

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

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

P(k+1)\displaystyle P(k+1) =2k+1+1+59k+1\displaystyle=2^{k+1+1}+5\cdot 9^{k+1} (6.7)
=22k+1+59k+1\displaystyle=2\cdot 2^{k+1}+5\cdot 9^{k+1} (6.8)
=2(P(k)59k)+59k+1\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 77 lurking somewhere!

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

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

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

6.3.2 From kk to k+1k+1

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

TODO: example