Mathematical induction

Kapitoly: What is a proof, Proof by contradiction, Mathematical induction

Mathematical induction is a frequently used method of proof in mathematics, most often when working with natural numbers or some other sequence.

Principle

The basic principle is that we prove a given statement for some first element, in natural numbers this is most often n = 1. We prove this by simple addition. In the next, inductive, step we prove the implication "if the statement holds for n = a, then it also holds for n = a + 1".

From these two steps, we can deduce that the expression holds for all n (from some set we are currently working with). Why is this so? At the beginning, we prove that the expression holds for n = 1. We also know that the expression holds for n = a and n = a + 1. So we choose a = 1. We know that the expression holds for a = 1, and we also know that it holds for a + 1 = 2. At this point, we know that the expression holds for a = 2. But since it holds for a + 1, it must also hold for 2 + 1 = 3. And so on.

The first example

The first example will be trivial. We will prove that if we add two to any even number, we get an even number again. Since we are dealing in natural numbers, we will write an even number in general as 2n, where n is a natural number. If we add any natural number after n, we get an even number in the result, this can be seen at a glance. Divisibility is written using a vertical line as follows:

$$2\mid2n$$

This notation indicates that two divides the expression 2n without remainder. Now that we can write divisibility, we can write what we have to prove by mathematical induction.

$$2\mid 2n+2; \quad n\in\mathbb{N}$$

This is what we are supposed to prove in the first example, that two divides the expression 2n + 2 - this is exactly what the original word problem says "if we add two to any even number, we get an even number again".

In the first step of the induction we prove this for the first element, one. We plug in the expression n = 1:

$$\begin{eqnarray} 2&\mid& 2\cdot1+2\\ 2&\mid& 4 \end{eqnarray}$$

Two divides four with no remainder, so this is true for the first element. Next comes the induction step, where we have to prove that if it holds for the a-th element, then it also holds for the (a + 1) element. At the beginning we assume that our assumption holds, i.e. n = a:

$$2\mid2a+2$$

We assume this expression to be true - we use it in the construction of the proof. We now want to prove that

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

What have we done? Instead of a we wrote (a + 1). The parentheses are important, this expression would be wrong: 2a + 1 + 2. We don't add a one to the whole expression, but really make a an expression one greater, i.e. (a + 1). We modify the expression by multiplying the parentheses.

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

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

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

We can put in, for example, the numbers p = 8, q = 20, and r = 4. We can see that four divides both eight and twenty. And so does their sum 8 + 20 = 28.

How do we use this in our example? Let's divide the right hand side into the numbers p and q as follows:

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

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

One more time about the assumption. We said at the beginning that we assume that

$$2\mid2a+2.$$

Therefore, when we came across the expression 2a + 2 during the construction of the proof, we could say that it is divisible by two. Precisely because it is our assumption. This is usually the hardest step of mathematical induction - understanding when and for which an inductive assumption can be used.

This ends the induction, the proof has been successfully carried out, the theorem holds.

If you wanted to, you could break it down differently and you wouldn't have to use the premise. p = 2n and q = 2 + 2. The number q = 4 is trivially divisible by four, and so is p = 2n, because after dividing by two we are left with n, which is natural, i.e., integer. So again we have two expressions that are both divisible by two, so their sum is also divisible by two.

But in both cases we have proved that

the given expression holds for n = 1,

if the expression holds for n, then it also holds for n + 1.

From here we can already derive:

We know that the expression holds for n = 1.
If it is valid for n, it must also be valid for n + 1, i.e. also for 1 + 1, i.e. the expression is also valid for n = 2.
If it holds for n, it must also hold for n + 1, i.e. also for 2 + 1, i.e. the expression holds for n = 3.
If it applies to n, it must also apply to n + 1, i.e. also to 3 + 1, i.e. the expression applies to n = 4.
If it applies to n, it must also apply to n + 1, i.e. also to 4 + 1, i.e. the expression applies to n = 5.
...

Second example

Next, we prove a simple statement by mathematical induction:

$$2^n\ge2n;\quad n\in\mathbb{N}.$$

First step one, we find out if the statement holds for n = 1, as the first element of the natural numbers from which n is selected.

$$\begin{eqnarray} 2^1&\ge&2\cdot1\\ 2&\ge&2 \end{eqnarray}$$

It trivially holds. Now we move on to the induction step, in which we have to see if if it holds for n = a, if it also holds for n = a + 1. So our assumption is that it holds

$$2^a\ge2a$$

and we want to prove:

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

We first break down the left-hand side using the rules of calculus with powers, and simply multiply the right-hand side.

$$2\cdot2^a\ge2a+2$$

In the left hand side we use addition instead of multiplication, and leave the right hand side unchanged.

$$2^a+2^a\ge2a+2$$

Now we will use the assumption. An assumption is a statement that we assume to be true. In the inequality, we have two expressions on each side that add up. At the same time, we know that

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

The first line tells us the assumption and the second statement is trivial (the lowest 2^a is for a = 1 and it equals just two). So we know that the two expressions on the left side are greater than or equal to the two expressions on the right side. Thus we have proved by induction that if an expression is true for a, then it is true for (a + 1), and since the expression is true for one, then the expression is true.

The third example

Let's try to prove the following statement:

$$3\mid n\Rightarrow 3\mid n^2;\quad n\in\mathbb{N}$$

Verbally: if n is divisible by three, then n² is also divisible by three. If n is not divisible by three, then the expression is trivially true (by definition of implication), so we will consider the cases where n is divisible by three. This will generate a sequence of natural numbers a_i=3, 6, 9, 12, 15... From now on, we will move through this sequence a_i.

We start the proof by induction with the first step, i.e. if it holds for the first element. Recall that we are moving in the sequence a_i, so we take the first element of this sequence, i.e., the element a₁, which is a three. For three, the expression holds:

$$3\mid3\Rightarrow 3\mid3^2$$

We now proceed to the induction step. We see that the sequence a_i could be written as 3n, where n is a natural number. Thus, the second element is three greater than the previous one, etc. Now suppose that the expression holds for n and we need to ensure that it also holds for (n + 3), which is a prescription that will generate the next element in the sequence we are moving through. Let's write down the assumption first:

$$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 decompose the bracket on the other side using the formula:

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

And we're almost there. On the left-hand side we have an expression that is definitely divisible by three, because n is divisible by three by assumption (we are only moving in the numbers of the sequence a_i), and three is also divisible by three. On the right-hand side we have first n², which by assumption is divisible by three. That is, we know that n is divisible by three, and the assumption says that if n is divisible by three, then n² is also divisible by three:

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

Then follows the expression 6n, which is trivially divisible by three. You can think of it as a contraction of a fraction:

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

The variable n is some natural number, so the product 2n will also be a natural number, i.e., after dividing by three we have a natural number, and so the expression 6n must be divisible by three. And the nine at the end is again divisible by three. The expression holds for the first element and for the induction step, so it is true.

The number of parentheses in the expression

The last example will be a bit untypical. Let's try to prove the claim that the number of parentheses in a simple expression is always even, so that you can see that mathematical induction can be used in a completely different context than just natural numbers. To begin with, we need to define what a simple expression is. A simple expression is:

a natural number,
if p is a simple expression, then (p²) is a simple expression,
if p and q are simple expressions, then (p + q) is a simple expression.

So what is a simple expression: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Conversely, these are not simple expressions:

1 + 2 $\rightarrow$ they are missing the outer parentheses,
(1 + 2 $\rightarrow$ missing right brackets,
13² $\rightarrow$ missing outside brackets,
(1 + 2 + 3) $\rightarrow$ missing brackets, the correct spelling should be (1+(2 + 3))

A simple expression can be formed, for example, as follows. At the beginning we choose the simple expression (a + b). Now after a we insert the simple expression a = (c + d), so we get ((c + d)+b) and after b we insert a triple: ((c + d)+3). After c we put a ten: ((10 + d)+3) and finally after d we put (5²): ((10+(5²))+3). It's important to follow the parentheses, otherwise it won't work.

Now we prove that the simple expression contains an even number of parentheses (even numbers include zero).

In the first step of the induction, we choose some first element. In this case, the first element will be the most trivial simple expression, which is an arbitrary natural number. So we put

$$j=n;\quad n\in\mathbb{N}.$$

For the expression j, the number of parentheses is zero, so the first element satisfies. In the induction step, we will assume that we have two simple expressions p and q and that they both have an even number of parentheses. Then we must prove that the simple expressions (p + q) and (p²) also have an even number of parentheses.

First the addition. We define another function z(q), which returns the number of parentheses of the expression q. Then the expression (p + q) has z(p)+z(q)+2 parentheses. That is, it has two more parentheses than the sum of the parentheses of the expressions p and q. By assumption, 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 holds.

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

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

Further resources and examples

« Previous: Proof by contradiction

Next: Calculus »