Mathematical induction

Mathematical induction is a widely used method of proof in maths, most often when we are working with the positive integers or with some other sequence.

The principle

The basic idea is that we prove the statement for a first element – with the positive integers this is most often n = 1. We do this by simple substitution. In the next step, the inductive step, we prove the implication “if the statement is true for n = a, then it is also true for n = a + 1”.

From these two steps we can conclude that the expression is true for all n (in whatever set we are working with). Why is that? At the start we prove that the expression is true for n = 1. We also know that if the expression is true for n = a, it is true for n = a + 1. So we choose a = 1. We know that the expression is true for a = 1, and we also know that it is true for a + 1 = 2. So now we know that the expression is true for a = 2. But because it is also true for a + 1, it must be true for 2 + 1 = 3. And so on.

First example

The first example is trivial. We prove that if we add 2 to any even number, we get an even number again. Since we are working with the positive integers, we write a general even number as 2n, where n is a positive integer. If we substitute any positive integer for n, the result is an even number – you can see that at a glance. Divisibility is written with a vertical bar like this:

$$2\mid 2n$$

This notation says that 2 divides the expression 2n with no remainder. Now that we can write divisibility, we can also write down what we are going to prove by induction.

$$2\mid 2n+2;n\in {\mathbb{Z}}^{+}$$

This is what we have to prove in the first example, that is, that 2 divides the expression 2n + 2 – exactly matching the original statement in words, “if we add 2 to any even number, we get an even number again”.

In the first step of the induction we prove it for the first element, for 1. We substitute n = 1 into the expression:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

2 divides 4 with no remainder, so it is true for the first element. Next comes the inductive step, in which we have to prove that if it is true for the ath element, then it is true for the (a + 1)th element. At the start we assume that our hypothesis holds, that is, n = a:

$$2\mid 2a+2$$

We assume that this expression is true – we will use it when constructing the proof. Now we want to prove that

$$2\mid 2(a+1)+2.$$

What have we done? We have written (a + 1) in place of a. The brackets are important – this expression would be wrong: 2a + 1 + 2. We are not adding 1 to the whole expression, but really turning a into something one bigger, that is, (a + 1). We simplify the expression by expanding the brackets.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Now a short detour on divisibility. If we have two numbers, say p and q, that are both divisible by some number, say r, then their sum is also divisible by r. So:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

For example, we can substitute p = 8, q = 20 and r = 4. We can see that 4 divides both 8 and 20. In the same way, it also divides their sum 8 + 20 = 28.

How do we use this in our example? We split the right-hand side into the numbers p and q like this:

$$p=2a+2;q=2$$

The number q, that is 2, is trivially divisible by 2. And the expression p is also divisible by 2, because our hypothesis tells us so. The expression p matches our hypothesis exactly, which we assume to be true. And if p is divisible by 2 and q is divisible by 2, then their sum is also divisible by 2.

Let us go over the hypothesis once more. At the start we said that we assume that

$$2\mid 2a+2.$$

So when we came across the expression 2a + 2 while constructing the proof, we could say that it is divisible by 2. That is precisely because it is our hypothesis. This is usually the hardest step of mathematical induction – understanding when and why the inductive hypothesis can be used.

That completes the induction: the proof is done and the theorem holds.

If you like, you could split it up differently and avoid using the hypothesis: p = 2n and q = 2 + 2. The number q = 4 is trivially divisible by 2, and so is p = 2n, because after dividing by 2 we are left with n, which is a positive integer, so in particular an integer. Again we have two expressions that are both divisible by 2, so their sum is divisible by 2 as well.

In both cases, though, we have proved that

1. the expression is true for n = 1,
2. if the expression is true for n, then it is also true for n + 1.

From this we can conclude:

• We know that the expression is true for n = 1.
• If it is true for n, it must be true for n + 1, that is, for 1 + 1, so the expression is true for n = 2.
• If it is true for n, it must be true for n + 1, that is, for 2 + 1, so the expression is true for n = 3.
• If it is true for n, it must be true for n + 1, that is, for 3 + 1, so the expression is true for n = 4.
• If it is true for n, it must be true for n + 1, that is, for 4 + 1, so the expression is true for n = 5.
• …

Second example

Next we use induction to prove a simple statement:

$$2^n\ge 2n;n\in {\mathbb{Z}}^{+}.$$

First the base case: we check whether the statement is true for n = 1, the first of the positive integers from which we choose n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

That is trivially true. Now we move on to the inductive step, in which we have to find out whether, if it is true for n = a, it is also true for n = a + 1. So our hypothesis is that

$$2^a\ge 2a$$

and we want to prove:

$$2^{a+1}\ge 2(a+1)$$

First we rewrite the left-hand side using the laws of indices and simply expand the brackets on the right-hand side.

$$2\cdot 2^a\ge 2a+2$$

On the left-hand side we use addition instead of multiplication and leave the right-hand side unchanged.

$$2^a+2^a\ge 2a+2$$

Now we use the hypothesis. The hypothesis is a statement that we assume to be true. In the inequality, both sides are sums of two terms. But we also know that

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

The first line is our hypothesis and the second statement is trivial (the smallest 2^a occurs at a = 1, and that is exactly 2). So each of the two terms on the left-hand side is greater than or equal to the corresponding term on the right-hand side. That proves by induction that if the expression is true for a, then it is true for (a + 1), and since the expression is also true for 1, the expression is true.

Third example

Let us try to prove the following statement:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{Z}}^{+}$$

In words: if n is divisible by 3, then n² is also divisible by 3. If n is not divisible by 3, the statement is trivially true (from the definition of implication), so we only need to deal with the cases where n is divisible by 3. That gives us the sequence of positive integers a_i=3, 6, 9, 12, 15… From now on we will stay within this sequence a_i.

We start the proof by induction with the base case, that is, whether it is true for the first element. Remember that we are moving within the sequence a_i, so we take the first element of this sequence, a₁, which is 3. For 3 the statement is true:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Now we move on to the inductive step. We can see that the sequence a_i could be written as 3n, where n is a positive integer. So each element is 3 more than the previous one, and so on. Now let us assume that the statement is true for n, and we need to make sure that it is also true for (n + 3), which is the rule that generates the next element of the sequence we are working in. First we write down the hypothesis:

$$3\mid n\Rightarrow 3\mid n^2$$

and then what we want to prove

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

We expand the bracket on the right-hand side using a formula:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

And now we are almost there. On the left-hand side we have an expression that is certainly divisible by 3, because n is divisible by 3 by the hypothesis (we are only working with numbers from the sequence a_i) and 3 is also divisible by 3. On the right-hand side we first have n², which by the hypothesis is divisible by 3. We know that n is divisible by 3, and the hypothesis says that if n is divisible by 3, then n² is divisible by 3 as well:

$$3\mid n\Rightarrow 3\mid n^2$$

Next comes the term 6n, which is trivially divisible by 3. You can think of it as simplifying a fraction:

$$\frac{6n}{3}=2n$$

The variable n is some positive integer, so the product 2n is a positive integer too. That is, after dividing by 3 we got a positive integer, so the term 6n must be divisible by 3. And the 9 at the end is again divisible by 3. The statement is true for the first element and for the inductive step, so it is true.

The number of brackets in an expression

The last example is a little unusual. We will try to prove that the number of brackets in a simple expression is always even, so that you can see that induction can be used in a completely different context from just the positive integers. First we need to define what a simple expression is. A simple expression is:

• a positive integer,
• if p is a simple expression, then (p²) is also a simple expression,
• if p and q are simple expressions, then (p + q) is also a simple expression.

So here are some simple expressions: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). And these are not simple expressions:

• 1 + 2 → the outer brackets are missing,
• (1 + 2 → the closing bracket is missing,
• 13² → the outer brackets are missing,
• (1 + 2 + 3) → brackets are missing; it should be written (1 + (2 + 3))

A simple expression can be built up like this, for example. We start by choosing the simple expression (a + b). Now we substitute the simple expression a = (c + d) for a, which gives ((c + d) + b), and for b we substitute 3: ((c + d) + 3). For c we substitute 10: ((10 + d) + 3), and finally for d we substitute (5²): ((10 + (5²)) + 3). It is important to keep the brackets, otherwise it will not work.

Now we prove that a simple expression contains an even number of brackets (zero counts as an even number).

In the first step of the induction we choose a first element. In this case the first element is the most trivial simple expression, which is any positive integer. So we put

$$j=n;n\in {\mathbb{Z}}^{+}.$$

For the expression j the number of brackets is zero, so the first element works. In the inductive step we assume that we have two simple expressions p and q and that both have an even number of brackets. Then we have to prove that the simple expressions (p + q) and (p²) also have an even number of brackets.

First, addition. Let us also define a function z(q) that returns the number of brackets in the expression q. Then the expression (p + q) has z(p) + z(q) + 2 brackets. So it has two more brackets than the sum of the brackets of p and q. By the hypothesis both z(p) and z(q) are even, so if we add three even numbers we get an even number again. For this case the statement is true.

Now the power. Again we assume that the simple expression p contains an even number of brackets. The expression (p²) then contains z(p) + 2 brackets, again two more than the expression p. In this case, too, we are adding even numbers, so the result is even.

The statement is true for the first element and also in the inductive step, so the statement is true.