# Principle of mathematical induction

Inductive reasoning is reasoning in which on the basis of a series of individual cases we make conclusion about the general rule. However, that conclusion does not have to be necessarily correct. Therefore, it also called the incomplete induction.

Mathematical induction is a method of proving that is used to demonstrate the various properties of natural numbers.

Principle of mathematical induction. If it is known that some statement is true for  and if from the assumption that it is true for some natural number implies that it is true for the next natural number , then the statement is true for every natural number .

The mathematical induction is given as the axiom, that is, it is the one of the Peano’s axioms given in the following form;

If such that:

1.) (B)

2.) (I)

then ,

that is, the set is equal to the set of natural numbers.

The step (B) is called the basis, and (I) is called the inductive step, that is, the proof we provide in two steps. In basis we prove that some statement is true for and in the inductive step from assumption that the statement is true for some we prove that the statement is also true for the next natural number  .

Example 1. Prove the formula for the sum of first natural numbers by using the principle of mathematical induction:

Solution:

We need to prove is it the given statement true for :

Therefore, the statement is true for .

Suppose  that the statement is true for some , that is, that for some the following is true:

Now we must prove that the statement is also true for , that is,  that for  the following is valid:

By using the assumption, we have:

Therefore, the statement is true for . By the axiom of mathematical induction, the statement is true for every natural number .

Example 2.

Prove that is valid:

Solution:

For

the statement is true.

Suppose that for some the statement is true, that is, that for some is true:

We must prove that the statement is also true for :

that is

By using the assumption, we have:

Therefore, the statement is true for . By the axiom of mathematical induction, the statement is true for every natural number .

The principle of the mathematical induction is applicable in many cases, and to prove various inequalities and divisibility of numbers.

Example 3. Prove that for all natural numbers  such that is valid:

Solution:

The statement is obviously true  for , because , that is .

Suppose that the statement is true for some natural number , that is

We need to prove that the statement is also true for , that is

By multiplying   with we obtain:

that is,

Because and , for every natural number from the previous inequality follows:

that is,

Therefore, the statement is true for . By the axiom of the mathematical induction the statement is true for every natural number .

Example 4. Prove that number

is divisible by , .

Solution:

For we have:

It follows that , therefore, the statement is true for .

Suppose that for some the following is true:

We need to prove that for the following is true:

that is

Then, by using the assumption, we have:

so the statement is true for . By the axiom of mathematical induction, the statement is true for .

Example 5.

Prove that , the following inequality is valid:

Solution:

The left side of inequality we will denote as , that is

We need to prove that the statement is true , therefore, in basis we have .

For we have

so the statement is true for .

Suppose that the statement is true for some .

We need to prove that the statement is also true for , that is

We will observing the difference between two consecutive adjacent members:

It follows

We obtain that , that is .

By applying the assumption we have:

Therefore, the statement is true for .

The statement is true for , and the assumption that the statement is true for some   implies that the statement is also true for , by the axiom of mathematical induction it follows that the statement is true , .

Example 6.

Prove that the following is valid:

Solution:

For we have

Therefore, the statement is true for .

Suppose that the statement is true for some :

We must prove that the statement is  also true for , that is:

By applying the assumption it follows:

Now we use the double angle formula for sine (). Therefore, we have:

The statement is true for , so by the principle of the mathematical induction, the statement is true .

Example 7.

Prove that is irrational number , .

Solution:

For we have

is irrational number is irrational number. Therefore, the statement is true for .

Suppose that for some the statement is true, that is, for some the number  is irrational.

We need to prove that the statement is true for , that is, for the number is irrational.

By using the half angle formula for cosine, we have:

Let’s assume the opposite, that is is the rational number.

Let .

After squaring we obtain

that is

which is the contradiction. Therefore, is an irrational number for such that .

Shares