Mathematical induction: how do you do it?

Understand the meaning of mathematical induction, its origin and how to apply it correctly to prove theorems involving natural numbers.

11/09/2023

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:

mathematical-induction

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:

mathematical-induction

is equals 3, and 3 is a prime number

mathematical-induction

is equals 5, and 5 is a prime number

mathematical-induction

is equals 17, and 17 is a prime number

mathematical-induction

is equals 257, and 257 is a prime number

mathematical-induction

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:

mathematical-induction

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:

mathematical-induction

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:

mathematical-induction

Square pyramidal numbers

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

mathematical-induction

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:

BASE:

T(n0)

We just need to prove that the theorem is valid for any initial n number.

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):

INDECTIVE STEP:

Hypothesis: If it is valid for a certain value k

Thesis: It must also be valid for the next value (k+1).

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 n0 value and then show that it is also valid for a k value and the next k+1 value. But how so?

mathematical-induction

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:

mathematical-induction

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

mathematical-induction

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.

mathematical-induction

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.

mathematical-induction

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 mathematical-induction itself.

mathematical-induction

Therefore we can substitute it in the equation.

mathematical-induction

We simplify the right side of the equation.

mathematical-induction

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

mathematical-induction

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

mathematical-induction

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

mathematical-induction

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:

mathematical-induction

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

mathematical-induction

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.

mathematical-induction

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.

mathematical-induction

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 k2 itself.

mathematical-induction

Therefore we can substitute it in the equation.

mathematical-induction

We simplify the left side of the equation.

mathematical-induction

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

mathematical-induction

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

mathematical-induction

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:

mathematical-induction
autor

David Santiago

Master in Systems and Computing. Graduated in Information Systems. Professor of Programming Language, Algorithms, Data Structures and Development of Digital Games.

Other articles