Mathematical induction: how do you do it?

Origin of mathematical induction

We can define as simply as possible mathematical induction (also known as finite induction) as the process that seeks to prove a particular theorem or property involving natural numbers (N = {0, 1, 2, 3, 4, 5, 6, …}).

Before addressing it, let’s look at the application of the vulgar induction technique, which was the usual way of proving theorems prior to the existence of mathematical induction. To do so, let’s look at Fermat’s number theorem. The theorem defines that:

is equal a prime number for any value of n

The mathematician Pierre de Fermat tried to prove his prime number theorem in the seventeenth century by this method. See below:

is equals 3, and 3 is a prime number

is equals 5, and 5 is a prime number

is equals 17, and 17 is a prime number

is equals 257, and 257 is a prime number

is equals 65535, and 65535 is a prime number

At first it seems that we have a pattern, an apparent rule. It seems that the proposed formula always generates prime numbers. But does this rule hold for all possible infinite values of n?

At first, the theorem was considered true only by demonstrating the first four values of natural numbers (vulgar induction). Until in 1732 the mathematician Leonhard Euler showed what is called in counterexample. Euler calculated the result of Fermat’s number to n = 5:

It turns out that this value found by Euler is not a prime number as it can be represented as 641 × 6,700,417. It is noteworthy that we are talking about a time when there were no computers and no calculating machines!

This counterexample overturned Fermat’s number theorem and showed the misconception of trying to prove properties of natural numbers by demonstrating some values. This shows not only the importance of not considering apparent initial results, but also the importance of using logically correct methods to prove formulas and theorems.

Some formulas and theorems

To understand the process of mathematical induction, we need to visualize some theorems on which we can apply it.

Summation of arithmetic progression

The theorem proposes a closed formula for the consecutive sum of the first n nonzero positive natural numbers:

Summation of first n odd numbers

The theorem proposes a closed formula for the consecutive sum of the first n odd, positive and nonzero natural numbers:

Square pyramidal numbers

The theorem proposes a closed formula for the consecutive sum of the square of the first n nonzero positive natural numbers:

However, we know that it is not possible to test all possible values of n to prove the validity of these theorems, because the natural numbers are infinite!

Note: You may have noticed the use of the summation symbol ∑ (sigma letter) in the formulas expressed above. If you do not know what a summation is yet, click here and access the article where we explain in detail about it.

Definition of mathematical induction

Mathematical induction is a technique used to prove a particular property that involves all infinite natural numbers. It consists of two basic principles: the base and the inductive step. First, we start by proving the basis:

After testing the base, we perform the inductive step, where we check if the theorem is valid for a given value k (hypothesis), and then verify if it is also valid for the next value k+1 (thesis):

That simple! The base and the inductive step represent the steps performed during the induction process. We show that the theorem is valid for an initial n₀ value and then show that it is also valid for a k value and the next k+1 value. But how so?

Imagine a domino effect: if it’s valid for 1 it’s valid for 1+1, i.e., it’s valid for 2. But if it’s valid for 2 it’s valid for 2+1, i.e., it’s valid for 3. But if it’s valid for 3 is valid for 3+1… In short, if the theorem is valid for one number and its successor, then the domino effect is proved and the theorem is valid for all infinite natural numbers.

It sounds like child’s play, but believe me, this is a perfectly valid logic for proving properties and theorems involving natural numbers.

Applying mathematical induction

Although it seems simple by definition, the induction process involves certain algebraic transformations that can complicate your head if not shown very carefully. For this reason, we will show you the step-by-step of this demonstration to prove the “sum of arithmetic progression” theorem, discussed in the previous session.

Prepare your spirit and come on:

The theorem determines the following formula for the consecutive sum of the first n positive non-zero natural numbers:

We start with the base, testing if the theorem is valid for n=3:

The value n=3 was just a guess, we could have used any value. The important thing is to show that the theorem is valid for a value.

Now we begin the inductive step by defining the hypothesis.

We start with the hypothesis that the theorem is valid for a value k.

We have previously demonstrated that this is valid!

If the theorem is valid for a given k value, then it must also be valid for the next value.

In this way we extend the equation. Now all we have to do is solve it algebraically and, in the end, make sure both sides are equal. Let’s solve:

Note that the green section below is nothing more than the theorem formula itself.

Therefore we can substitute it in the equation.

We simplify the right side of the equation.

On the left side, we place the parcels under the same common denominator.

Note that (k+1) repeats in both plots. So we can put it in evidence.

We reduce the equation and show that both sides are equivalent.

Ready! The induction has been completed and we have proved that the sum theorem works for all infinite non zero positive natural numbers.

Another example of mathematical induction

Let’s do the mathematical induction for one more example, so you can understand more clearly how the process happens. This time, we’ll use it to prove the “sum of n first odd numbers” theorem:

The theorem reports a closed formula for the consecutive sum of the first nonzero positive natural odd numbers:

We start with the base, testing if the theorem is valid for n=3:

Now we begin the inductive step by defining the hypothesis.

We start with the hypothesis that the theorem is valid for a given value k.

We have previously demonstrated that this is valid!

If the theorem is valid for a given k value, then it must also be valid for the next value.

In this way we extend the equation. Now all we have to do is solve it algebraically and, in the end, make sure both sides are equal. Let’s solve:

Note that the green section below is nothing more than theorem formula k² itself.

Therefore we can substitute it in the equation.

We simplify the left side of the equation.

A number multiplied by itself is the same as it squared. So we turn the right side of the equation into two factors.

We reduce the equation and show that both sides are equivalent.

Ready! The induction has been completed and we have proved that the theorem works for all infinite positive, odd and nonzero natural numbers.

Now it’s your turn!

Show that you have learned the induction process and prove the theorem below: