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

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

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.

### Sum of arithmetic progression

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

### Sum 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:

**Base:**

**n**

_{0})

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

**Inductive step:**

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**_{0} 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 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:

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

**k**itself.

^{2}**k**and extract in two factors (k+1)

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: