Proof by mathematical induction: introduction

written in maths

I’m currently studying abstract mathematics for my maths degree, which involves learning how to prove all sorts of statements. One type of proof I really struggled with initially was proof by mathematical induction. However, after being recommended the wonderful Book of Proof by Richard Hammack, this method of proving statements finally clicked for me. As such I decided to create a few blog posts to hopefully help anyone who is similarly stuck (and help me to remember myself!).

Motivating example

Let’s say that we wish to prove that the sum \(1 + 2 + 3 + 4 + \ldots + n\) is equal to \(\frac{n^2 + n}{2}\) for every positive integer \(n\). Where do we start? We could break down this statement for each case of \(n\) like so:

$$S_n$$ $$\textrm{Sum of first } n \textrm{ positive numbers}$$ $$\frac{n^2 + n}{2}$$
$$S_1$$ $$1$$ $$1$$
$$S_2$$ $$1 + 2$$ $$3$$
$$S_3$$ $$1 + 2 + 3$$ $$6$$
$$S_4$$ $$1 + 2 + 3 + 4$$ $$10$$
$$S_5$$ $$1 + 2 + 3 + 4 + 5$$ $$15$$

We can see that the statement is true for the first 5 cases, but the problem is that we have to prove this for all positive numbers, which is an infinite set. Even if we had the time and inclination to go through and prove each case individually, we’d never be able to reach the end! We need to instead come up with some sort of rule that will generalise to every statement \(S_n\).

This is exactly what proof by induction is designed to do. To begin, we prove that the first possible statement is true. In our case, we are dealing with positive integers, so the first possible statement is \(S_1\). We’ve already done this in the table above, showing that \(1 =\frac{ (1^2 + 1)}{2} = \frac{2}{2} = 1\). This is called the basis step.

We can now move onto proving that all \(S_n\) are true, using what is called the inductive step. This step uses the fact that we know one statement to be true (in our case, \(S_1\)), and shows that this implies the next statement to be true. However, we want to prove this for all \(S_n\), so we need to extend our solution beyond just \(S_1\) and \(S_2\). To do so, we generalise our basis step \(S_1\) to be \(S_k\), use the fact we know it is true, and prove that if \(S_k\) is true, then \(S_{k + 1}\) is also true (in other words, we aim to prove the conditional statement \(S_k \Rightarrow S_{k + 1}\)). This results in a sort of domino effect, where if the first pair of \(S_k \Rightarrow S_{k + 1}\) is true, then this means that \(S_{k + 1} \Rightarrow S_{k + 2}\) is also true, and so on, covering all possible statements \(S_n\).

In our example, this means that if:

$$ 1 + 2 + 3 + \ldots + k = \frac{k^2 + k}{2} $$

then:

$$ 1 + 2 + 3 + \ldots + k + (k + 1) = \frac{(k + 1)^2 + (k + 1)}{2} $$

.

(All that we’ve done in the above two statements is substitute in \(k\) instead of \(n\) in the first statement, and \(k + 1\) instead of \(n\) in the second statement.)

We now know one fact, that our first statement above is true. We must now prove the second statement by showing that the lefthand side is equivalent to the righthand side. This looks like quite a sticky algebraic problem. However, we can use what we already know to our advantage to simplify the expression. The lefthand part of the equation is comprised of \((1 + 2 + 3 + \ldots + k) + ((k + 1))\). As we know that \(1 + 2 + 3 + \ldots + k\) is the same as \(\frac{k^2 + k}{2}\), we can substitute in this expression. The rest is now a matter of using algebra to rearrange each side of the equation until they are equal. This is usually a matter of trial and error, but you can see some patterns that will help guide your work. In this example, the lefthand side contains a squared term, which means we’re probably going to have to expand the quadratic equation on the righthand side.

$$ \begin{aligned} 1 + 2 + 3 + \ldots + k + (k + 1) &= \frac{(k + 1)^2 + (k + 1)}{2} \\ \frac{k^2 + k}{2} + (k + 1) &= \frac{(k + 1)^2 + (k + 1)}{2} \\ k^2 + k + 2(k + 1) &= (k + 1)^2 + (k + 1) \\ &= k^2 + 2k + 1 + k + 1 \\ &= k^2 + k + 2(k + 1) \end{aligned} $$

And voilà! We have shown that, if we assume our first statement \(S_k\) to be true, then the subsequent statement \(S_{k + 1}\) is also true. Using the logic described above, we can then say that this is true for all \(S_n\).

A more formal example

Let’s round off this blog post by showing how a proof by induction could be laid out formally. We’ll take a new problem. Let us say that we wish to prove that the sum \(a + ar + ar^2 + \ldots + ar^{n - 1}\) is equal to \(a\frac{1 - r^n}{1-r}\), where \(r \neq 1\) and \(n \in \mathbb{N}\). As \(n \in \mathbb{N}\), this is exactly the same as the previous example, where \(n\) is in the positive integers. This means our basis step will be the smallest element of that set, \(n = 1\). Let’s get started with laying out the proof.

Proof:
(1) Basis step. Observe that when \(n = 1\), then:

$$ \begin{aligned} ar^{1 - 1} &= a\frac{1 - r^1}{1 - r} \\ a^0 &= a \cdot \frac{1 - r}{1 - r} \\ a &= a \end{aligned} $$

(2) Inductive step. Say that \(k \geq 1\). We will use direct proof to show that if:

$$ar^{1-1} + ar^{2-1} + ar^{3-1} + \ldots + ar^{k-1} = a\frac{1 - r^k}{1 - r}$$

then:

$$ar^{1-1} + ar^{2-1} + ar^{3-1} + \ldots + ar^{k-1} + ar^{(k + 1) - 1} = a\frac{1 - r^{k + 1}}{1 - r}$$

.

Suppose that \(ar^{1-1} + ar^{2-1} + ar^{3-1} + \ldots + ar^{k-1} = a\frac{1 - r^k}{1 - r}\). Then:

$$ \begin{aligned} ar^{1-1} + ar^{2-1} + ar^{3-1} + \ldots + ar^{k-1} + ar^{(k + 1) - 1} &= a\frac{1 - r^{k + 1}}{1 - r} \\ a\frac{1 - r^k}{1 - r} + ar^{(k + 1) - 1} &= a\frac{1 - r^{k + 1}}{1 - r} \\ \frac{1 - r^k}{1 - r} + r^k &= \frac{1 - r^{k + 1}}{1 - r} \\ 1 - r^k + r^k(1 - r) &= 1 - r^{k + 1} \\ 1 - r^k + r^k - r^{k + 1} &= 1 - r^{k + 1} \\ 1 - r^{k + 1} &= 1 - r^{k + 1} \end{aligned} $$

It follows by induction that \(ar^{1-1} + ar^{2-1} + ar^{3-1} + \ldots + ar^{n-1} = a\frac{1 - r^n}{1 - r}\) for each \(n \in \mathbb{N}\).

And that’s it! It takes a bit of practice to get used to the steps, but the core of mathematical induction is proving the statement \(S_k \Rightarrow S_{k+1}\), which usually ends up being a relatively straightforward direct proof. In the next blog post, I’ll cover how to prove by induction when the statement is written as a summation formula.