Induction

Section 7.1 Induction

Induction, once you get past some of the technicalities, is a very intuitive idea. This author likes to think of induction like climbing an infinite ladder and an induction argument is really just a proof that we can climb that ladder. The proof is in 3 parts:

If you can step onto the ladder, and

🔗
from the current step you can reach the next step, then

🔗
you can climb the ladder as high as you want.

🔗

🔗

As more concrete mathematical example, say we wish to prove

\begin{equation*} \text{For all } n \in \mathbb{N}, n^2+5n-7 \text{ is odd}. \end{equation*}

The dedicated reader may recall a very similar example in Chapter 5 and realise that we can do this using proof by cases, however, it is a good example for proof by “ladder idea”.

Step onto the ladder. When \(n=1\) the polynomial is \(1+5-7 = -1\) which is odd. So the assertion is true for the very smallest value of \(n\text{.}\)
🔗

🔗
Climb from one rung to the next. We wish to show that if the assertion is true for the current value of \(n=k\text{,}\) then it is also true for \(n=k+1\text{.}\) That is, if we are on the current step, we can move up to the next step. So, to be more precise, we want to show that

\begin{equation*} (k^2+5k-7 \text{ is odd}) \implies ( (k+1)^2+5(k+1)-7 \text{ is odd}) \end{equation*}

So this is just a little direct proof hiding inside our argument.

🔗

Proof: Assume \(k^2+5k-7 = 2\ell+1\text{.}\) Then

\begin{align*} (k+1)^2+5(k+1)-7 \amp= k^2+2k+1+5k+5-7 \\ \amp= \underbrace{k^2+5k-7}_{=2\ell+1} + (2k+6) \\ \amp= 2(\ell+k+3) + 1. \end{align*}

Hence \((k+1)^2+5(k+1)-7\) is odd as required.

🔗

🔗
Conclusion. So how do we put these facts together? The first fact guarantees that our result is true for \(n=1\text{.}\) Then the second fact tells us that since it is true for \(n=1\text{,}\) it is also true for \(n=2\text{.}\) But then since it is true for \(n=2\text{,}\) it true for \(n=3\) (by the same fact). Applying that fact again and again gives us \(n=4, n=5, n=6, \cdots\text{.}\)
🔗

🔗

Strictly speaking we have to be a bit more careful with that final “…”, but we’ll see how to do that below.

🔗

This proof method, mathematical induction, is formalised in the next theorem.

🔗

Theorem 7.1.1. The principle of mathematical induction.

For every \(n \in \mathbb{N}\) let \(P(n)\) be a statement. If

\(P(1)\) is a true statement, and

🔗
the implication \(P(k) \implies P(k+1)\) is true for all \(k \in \mathbb{N}\)

🔗

then \(P(n)\) is true for all \(n \in \mathbb{N}\text{.}\)

🔗

We can’t quite give a complete proof of this theorem, though we can give almost everything that is needed. Call this a “proof sketch” — the core ideas are there, but we’ll skip over a technicality and also write it a little informally.

🔗

Proof-sketch.

Start by assuming the hypotheses of the theorem are true. That is, we assume that

\(P(1)\) is true, and

🔗
the implication \(P(k) \implies P(k+1)\) is true for all natural numbers \(k\text{.}\)

🔗

🔗

Then the core idea of the proof is construct two sets

The “good” set:

\begin{equation*} G = \set{n \in \mathbb{N} \mid P(n) \text{ is true} } \end{equation*}

This is the set of all \(n\)-values for which our statement is true. By assumption, we know that \(1 \in G\text{,}\) and \(G \neq \es\text{.}\)

🔗

🔗
The “bad” set:

\begin{equation*} B = \set{n \in \mathbb{N} \mid P(n) \text{ is false} }. \end{equation*}

This is the set of all \(n\)-values for which our statement is false.

🔗

🔗

As is often the case, the “good” isn’t as interesting as the “bad”, and we’ll focus on the set \(B\text{.}\) It is either empty or non-empty.

🔗

If \(B\) is empty, then we are done, because then \(P(n)\) must be true for every single \(n\in \mathbb{N}\) as required.

🔗

As \(B\) is not empty, we can look for the smallest element in \(B\text{.}\) And since \(B\) is a non-empty set of natural numbers we can always find its smallest smallest element. However we do note that this is not possible for all sets — we’ll come back to this point shortly.

🔗
Let \(\ell\) be this smallest number in \(B\text{.}\)

🔗
From the hypothesis in the theorem, we know that \(\ell \gt 1\) (since \(P(1)\) is true).

🔗
By the way we constructed \(B\) and \(\ell\text{,}\) we know that \(P(n)\) is true for all \(1 \leq n \lt \ell\text{.}\)

🔗
Now we have a problem:
- we know that \(P(\ell-1)\) is true, but
  
  🔗
- we also know that the implication \(P(\ell-1) \implies P(\ell)\) is true (since that is one of the hypotheses).
  
  🔗
- But if \(P(\ell-1)\) is true, and \(P(\ell)\) is false, then that implication is false.
  
  🔗
🔗
🔗
This is a contradiction — our assumption is contradicted by \(P(\ell)\) being false.

🔗
The only way to resolve this situation is to conclude that no such \(\ell\) exists — that is, \(B\) is empty.

🔗

Hence we must have \(P(n)\) is true for all natural numbers \(n\)

🔗

There are two sneaky things going on in this proof. Firstly, we are doing a proof by contradiction by stealth; don’t worry too much about this yet as we’ll return to those proofs later in the text. Second, and more important in the short term, is that the proof relies on a delicate point

🔗

since \(B\) is just a non-empty set of natural numbers, we can always find the smallest number in that set.
🔗

🔗

We are using here something called the well ordering principle. This guarantees us that we can always find the smallest element in a set of natural numbers. This is very definitely false for other sets of numbers — if we build a set of integers, or rational numbers, or real numbers, then it might not have a minimum.

🔗

Example 7.1.2. Sets without minima.

Consider the following sets

\begin{align*} \set{2k \mid k \in \mathbb{Z} } && \set{\frac{1}{n} \mid n \in \mathbb{N}} && (0,1) = \set{x \in \mathbb{R} \mid 0 \lt x \lt 1}. \end{align*}

None of these sets have minimum elements; you can always find another element that is smaller.

🔗

Solution.

Note that this argument requires proof by contradiction and if the reader is confused by the details of this argument, we suggest that they wait until we have covered that topic and then return to this discussion. In fact, making this an example in that section is a good idea and the authors might do exactly that.

🔗

Consider the set \(\set{2k \mid k\in\mathbb{Z}}\text{.}\)

Either this set has a minimum or it does not.

🔗
If it does have a minimum, call that minimum \(\ell\text{.}\)

🔗
However, the number \(\ell-2\) is also in the set, and \(\ell-2 \lt \ell\text{.}\)

🔗
So \(\ell\) cannot be the minimum.

🔗

So the set cannot have a minimum.

🔗

Similarly, if \((0,1)\) has a minimum then call it \(q\text{.}\) But then since \(0 \lt q \lt 1\text{,}\) we know that \(0 \lt q/2 \lt q\text{.}\) So \(q/2\) is in the set and smaller than \(q\text{,}\) so \(q\) cannot be a minimum. Hence no such minimum exists. The same argument works for the set \(\set{1/n \mid n\in\mathbb{N}}\text{.}\)

🔗

Now that we are armed with a formal statement of mathematical induction, we should make use of it. The typical first example is the simple summation we saw in the introduction to this chapter. However (arguably) this can give the wrong idea of what induction is. To (hopefully) avoid this potential trap, let us do an example about divisibility.

🔗

Result 7.1.3.

For every natural number \(n\text{,}\) \(3 | (4^{n}-1)\text{.}\)

🔗

So our statement is \(P(n)\) is “\(3 | (4^{n}-1)\)”. To prove this true for all naturals \(n\) using induction, we need to show

The statement \(P(1)\) is true, and

🔗
The implications \(P(k) \implies P(k+1)\) is true for all \(k \in \mathbb{N}\text{.}\)

🔗

In most cases (but definitely not all), showing that \(P(1)\) is true is easy, and proving the inductive step requires work.

Setting \(n=1\) in our statement gives
\begin{gather*} 3|(4^1-1) \end{gather*}
which is true (since \(4-1=3\)).

🔗
Now the harder part — the inductive step: We have to prove that
\begin{gather*} ( 3 | (4^k-1)) \implies (3|(4^{k+1}-1)) \end{gather*}
for all \(k\in \mathbb{N}\text{.}\) That is, the inductive step requires us to prove an implication. As we have done many times before (and will do many times in the future), we assume the hypothesis is true and work our way to the conclusion. So we start by assuming that \(3|(4^k-1)\text{,}\) which means that
\begin{align*} 4^k-1 &= 3 \ell & \text{for some } \ell \in\mathbb{Z} \end{align*}
and we want to arrive at
\begin{align*} 4^{k+1}-1 &= 3m & \text{so that } \amp\amp 3|(4^{k+1}-1) \end{align*}
We need to think about how we can construct \(4^{k+1}-1\) from \(4^k-1\text{.}\) Multiplying by 4 is a good way to go:
\begin{align*} 4^k-1 &= 3\ell\\ 4^k &= 3\ell+1\\ 4^{k+1} &= 12\ell +4\\ 4^{k+1}-1 &= 12\ell +3 = 3(4\ell+1) \end{align*}
And since \(4\ell+1 \in \mathbb{Z}\) we have reached the conclusion we want.

🔗

🔗

Now that we know how to prove the base case (that was easy) and we know how to prove the inductive step (not too bad), we can put things together into a proof. Remember to tell the reader what we are doing.

🔗

Proof.

We proceed by induction.

Base case — When \(n=1\) the result is true since \(3|(4-1)\text{.}\)

🔗
Inductive hypothesis — Assume \(P(k)\) is true. Then \(4^k-1 = 3 \ell\) for some \(\ell \in \mathbb{Z}\text{.}\) Then
\begin{align*} 4^{k+1}-1 &= 4(4^k)-1\\ &= 4(4^k-1)+4-1\\ &= 4\cdot 3 \ell +3 = 3( 4\ell +1) \end{align*}
Thus if \(P(k)\) then \(P(k+1)\text{.}\)

🔗

By the principle of mathematical induction the statement is true for all naturals \(n\text{.}\)

🔗

Remark 7.1.4. Make structure obvious to the reader.

Notice that we are making the structure of the proof very clear. We start by telling reader that we are using induction. We have then labelled the two conditions “base case” and “inductive hypothesis” or “inductive step”, so that it is very clear how the proof is being constructed. We then have a little summarising sentence at the end saying “by induction it is true!” It means that a reader who is familiar with induction can readily check off each part of the induction proof against what they know about induction as they read the proof. We make it easy for them to read and verify the proof. (This is an especially good idea when someone has to mark your work, not just read it!)

🔗

We can rewrite our above simple parity example with this same structure. It is good practice.

🔗

Example 7.1.5.

For all \(n \in \mathbb{N}, n^2+5n-7\) is odd.

🔗

Solution.

Proof.

We use induction to prove the result.

Base case. When \(n=1\text{,}\) the polynomial gives \(1+5-7 = -1\text{.}\) Hence the base case is true.

🔗
Inductive step. Assume that \(k^2+5k-7\) is odd, and so \(k^2+5k-7 = 2\ell+1\text{.}\) Then

\begin{equation*} (k+1)^2 + 5(k+1)-7 = 2k+6 + (k^2+5k-7) = 2(k+3)+2\ell+1 \end{equation*}

and hence is also odd.

🔗

🔗

By mathematical induction the result holds for all \(n \in \mathbb{N}\text{.}\)

🔗

Aside: Extend to all \(n \in \mathbb{Z}\).

To avoid doing the very standard summation examples for a touch longer, we’ll do an inequality. This particular example is another classic induction problem

⁷²

Like many of the authors “jokes” it is an antique and should be handled with care.

🔗

Result 7.1.6.

Let \(n \in \mathbb{N}\) and let \(x\in\mathbb{R}\) with \(x \gt -1\text{.}\) Then

\begin{equation*} (1+x)^n \geq 1+nx. \end{equation*}

🔗

If we choose to use induction (and we will), then it is a good idea to clarify what the actual statement is. Rewriting things carefully, we can write

\begin{equation*} P(n): \text{if } (x \gt -1) \text{ then } (1+x)^n \geq (1+nx). \end{equation*}

First up, we verify the base case; setting \(n=1\) gives

\begin{gather*} (x \gt -1) \implies (1+x)^1 \geq 1+x \end{gather*}

Since \((1+x)^1 = 1+x\text{,}\) the conclusion is always true, so the implication is true, and the base case is true.

🔗

🔗
Now the induction step. We assume that \(P(k)\) is true. That is

\begin{gather*} (x \gt -1) \implies (1+x)^k \geq 1+kx \end{gather*}

is a true statement, and we then need to prove that

\begin{gather*} (x \gt -1) \implies (1+x)^{k+1} \geq 1+(k+1)x. \end{gather*}

To prove this second implication, we do as we have done so many times, and will do many times in the future, we assume the hypothesis is true. So we assume \((x \gt -1)\text{.}\) From the first implication (and our assumption that \(x\gt -1\)) we know that \((1+x)^k \geq 1+kx\text{.}\) We now need to prove that \((1+x)^{k+1}\) is bigger than \(1+(k+1)x\text{.}\)

🔗

A good place to start is to take the inequality we know and try to make it look like the inequality we want.

\begin{align*} (1+x)^k &\geq 1+kx & \text{multiply by } (1+x)\\ (1+x)^{k+1} & \geq (1+kx)(1+x)\\ &= 1+(k+1)x + kx^2 \end{align*}

Nearly there, we just need to get rid of this \(kx^2\) term. We know \(x^2 \geq 0\text{,}\) so \(kx^2 \geq 0\) and hence

\begin{align*} (1+x)^{k+1} \amp \geq 1+(k+1)x + kx^2 \geq 1+(k+1)x \end{align*}

as required.

🔗

But there is a problem: where have we used the assumption \(x \gt -1\text{?}\)
🔗

When you are doing mathematics and answering problems, you should keep your eyes open for this sort of thing. If you haven’t used one of the hypotheses in your proof then there is very likely to be an error somewhere!
🔗

Now — our work above is not actually wrong, but that is more by luck than by design
⁷³
Of course the author actually designed the example to illustrate this luck. So perhaps it is designed luck?
. Where we multiplied by \(1+x\) we didn’t examine whether quantity is positive or negative. When we multiply an inequality by something positive (say \(+2\)), then inequality keeps the same sign:

\begin{align*} 2 & \leq 3 & \implies 4 & \leq 6. \end{align*}

but when we multiply by something negative (say \(-2\)), the sign flips:

\begin{align*} 2 & \leq 3 & \implies (-4) & \geq (-6) \end{align*}

Thankfully since \(x \gt -1\text{,}\) we know that \(1+x \gt 0\) and so we are not multiplying by a negative number. We don’t have to go back and fix our scratchwork, but we should make sure that we highlight this point when we write up the proof. We help our reader understand important subtle details by pointing them out.

🔗

🔗

🔗

Proof.

We use induction.

Based case: when \(n=1\text{,}\) the statement is true since \((1+x)^1 = 1+1\cdot x\text{.}\)

🔗
Induction step. We assume that \(x \gt -1\) and that \((1+x)^k \geq 1+kx\text{.}\) Since \(x \gt -1\text{,}\) we know that \(1+x \gt 0\) and so multiplying through by \(1+x\) doesn’t change the sign of the inequality:
\begin{align*} (1+x)^k(1+x) &\geq (1+kx)(1+x) \amp \text{factor left and expand right}\\ (1+x)^{k+1} & \geq 1+(k+1)x + kx^2 &\text{since }x^2\geq 0\\ &\geq 1+(k+1)x \end{align*}
as required.

🔗

So by induction the inequality is true for all \(n\in\mathbb{N}\text{.}\)

🔗

Now we are ready to do the very standard summation example. But first a warning

⁷⁴

A nag?

🔗

Warning 7.1.7. Induction is not summation.

Induction requires us to prove both that

the base case, \(P(1)\text{,}\) is true, and

🔗
the inductive hypothesis, \(P(k)\implies P(k+1)\text{,}\) is true for all \(k\in\mathbb{N}\text{.}\)

🔗

Mathematical induction is not simply adding the next term to both sides of the equation.

🔗

With that out of the way:

🔗

Result 7.1.8.

For every natural number \(n\text{,}\) \(\sum_{k=1}^n k = \frac{n(n+1)}{2}\)

🔗

The base case is very easy (as it often is). When \(n=1\) we have:
\begin{align*} \sum_{k=1}^n k &= \frac{1\cdot 2}{2} & \text{which is}\\ 1 &= 1 \checkmark. \end{align*}

🔗
As is typical, the inductive step needs a bit more work. We need to prove that
\begin{align*} \left( 1 + 2 + \cdots + k = \frac{k(k+1)}{2} \right) & \implies \left( 1 + 2 + \cdots + k + k+1 = \frac{(k+1)(k+2)}{2} \right) \end{align*}
Like most proofs of implications, we start by assuming the hypothesis is true and try to work our way to the conclusion. In this case, it is pretty clear that we can get from the first statement to the second just by adding \((k+1)\) to both sides. Note that “adding \(k+1\) to both sides” is not the induction step. The induction step requires us to prove that \(P(k) \implies P(k+1)\text{,}\) and we prove that in this particular example by adding \(k+1\) to both sides. This is a very common error (and more than a little frustrating to mark
⁷⁵
Be nice to your marker?
).

🔗

We are now ready to write things up nicely.

🔗

Proof.

We proceed by induction.

Base case — When \(n=1\) the statement is true since \(1 = \frac{1 \cdot 2}{2}\text{.}\)

🔗
Inductive hypothesis — Assume the statement is true for \(n=k\text{,}\) that is
\begin{align*} 1 + 2 + \cdots + k &= \frac{k(k+1)}{2} \end{align*}
Adding \(k+1\) to both sides gives
\begin{align*} 1 + 2 + \cdots + k +(k+1) &= \frac{k(k+1)}{2} + (k+1)\\ &= \frac{1}{2} \left(k^2+k + 2k +2 \right)\\ & = \frac{1}{2} (k+1)(k+2). \end{align*}
Hence if the statement is true for \(n=k\) then it must be true for \(n=k+1\text{.}\)

🔗

By the principle of mathematical induction it is true for all natural numbers \(n\text{.}\)

🔗

It is a good idea to see a few false induction proofs. Each of these examples contains a flaw.

🔗

Example 7.1.9. Polynomial primes.

For all \(n \in \mathbb{N}, n^2-n+41\) is prime.

🔗

We call the following argument a “misproof” since it looks like a proof, but is incorrect. In the solution below we explain why it is wrong.

🔗

Misproof.

We check the first values of \(n\text{:}\)

\(n=1\text{:}\) \(1-1+41 = 41\) which is prime.

🔗
\(n=2\text{:}\) \(4-2+41 = 43\) which is prime.

🔗
\(n=3\text{:}\) \(9-3+41 = 47\) which is prime.

🔗
\(n=4\text{:}\) \(16-4+41 = 53\) which is prime.

🔗
\(n=5\text{:}\) \(25-5+41 = 61\) which is prime.

🔗

Since it is true for the first few values of \(n\text{,}\) it is true for all \(n\text{.}\)

🔗

Solution.

This is a very wrong proof. Examples are not proof.

🔗

Surprisingly this polynomial does give you prime numbers for \(n=1,\cdots,40\text{.}\) This was first noticed by Euler

⁷⁶

The interested reader should search-engine their way to “Euler’s lucky numbers”. There is actually some quite deep number theory lurking in side that polynomial.

. However when \(n=41\) it is clearly not prime, since it gives \(41^2-41+41 = 41^2\text{.}\)

🔗

Example 7.1.10. Everything you know about 2 is wrong?

For all \(n \in \mathbb{N}\text{,}\) \(n+1 \lt n\text{.}\)

🔗

We give the flawed proof and then explain what is wrong with it in the solutions below.

🔗

Misproof.

We prove this by induction. So assume that the statement is true for \(n=k\text{.}\) That is

\begin{equation*} k+1 \lt k. \end{equation*}

Then we can write, by adding \(1\) to both sides of the above inequality

\begin{equation*} (k+2) \lt (k+1) \end{equation*}

And thus the statement is true for \(n=k+1\text{.}\) By mathematical induction, the statement is true for all \(n \in \mathbb{N}\text{.}\)

🔗

Solution.

This proof of the inductive step is perfectly correct. We have correctly shown that

\begin{equation*} (k+1 \lt k) \implies (k+2 \lt k+1) \end{equation*}

However this is a vacuous statement since the hypothesis is never true. This is the flaw in our proof — we did not check the base-case. When \(n=1\) the statement is false.

🔗

Since the base case fails, we cannot use mathematical induction. Both the base case and the inductive step must be true for an induction proof to work.

🔗

Example 7.1.11. Pólya’s colourless horses.

This is George Pólya’s proof that “All horses have the same colour”.

🔗

Again, we’ll first give the flawed proof, and then show you where it goes wrong.

🔗

Misproof.

We proceed by induction.

Base case: When there is only 1 horse, it has the same colour as itself. So the statement is true when there is exactly 1 horse.

🔗
Inductive step: We assume the statement is true when there are \(n=k\) horses. Now consider a set of \(n=k+1\) horses. Exclude one of those horses from the set to obtain a set of \(k\) horses. By assumption all those horses have the same colour. Put that excluded horse back into the set and remove another. Now the set again has \(k\) horses and so they all have the same colour. This means that all the \(k+1\) horses (including the two we temporarily removed) must have the same colour.
🔗

🔗

By induction the statement is true for all \(n \in \mathbb{N}\text{.}\)

🔗

Solution.

So what is wrong here? There is a subtle error in the inductive step. Remember that the inductive step has to be true for all \(k \in \mathbb{N}\text{,}\) however it contains the tacit assumption that \(k\) is not too small. To see why, step through the argument carefully when \(k=1\text{.}\)

🔗

Assume that the statement is true when \(n=k=1\text{.}\) Then consider a set of \(n=k+1 = 2\) horses: call them Alice and Bob

⁷⁷

Very traditional names for horses with side-interests in cryptography.

. Now we remove one horse (Alice), and then every horse remaining in the set (which is just Bob) has the same colour. Now we put Alice back and take Bob out. So Alice has the same colour as every horse in the set — which is just Alice. At no point do we ever compare the colour of Alice or Bob with a third horse

⁷⁸

A stalking horse? A dark horse?

. Consequently we cannot infer any relationship between the colours of equine Alice or Bob.

🔗

Prev Top Next