Mathematics THE PRINCIPLE OF MATHEMATICAL INDUCTION

Introduction :

In algebra, there are certain results that are formulated with n number of terms in them, where n is a natural number (i.e. a positive integer). Those results can be proved by a specific technique, known as the principle of mathematical induction. We use the symbol `P(n)` (read `"P` of `n"` ) to denote some proposition which depends on the positive integer `n`. For example, `P(n)` might denote the sum of the first n odd positive numbers, that is

`1 + 3 + 5 + 7 + 9 + ...... + (2n - 1) = n^2`

where `n = 1 , 2, 3, .......... , n` .

First Principle of Mathematical Induction :

The proof of the proposition `P(n)` by mathematical induction for all `n in N` consists of the following three

steps:

Step-1. Verification step :

Verify that the proposition `P(n)` is true for `n = 1` , i.e. , the first natural number or the smallest positive integer. This is also called the basic step of the induction.

Step-2. Induction step :

Assume that the proposition will also be true for some `n = k ge 1` , i.e. we assume `P(k)` to be true. This is called the induction step.

Step-3. Generalization step :

If `P(k)` is true, then prove that the proposition is also true for `n = (k+ 1)`, which is the next positive integer (i.e. the next natural number), i.e. we have to prove that `P(k + 1)` must also be true. In this step we prove that the implication `P(k) => P(k + 1)` is true. Next we generalize the result by saying that, since the proposition is proved to be true for `n = k+ 1` , then it must also be true for `n = k`, and hence the proposition will be true for all `n` belonging to the set of natural numbers.

Second Principle of Mathematical Induction :

Step-1. Verification step :

Verify that the proposition `P(n)` is true for `n = r`, where `r` is some fixed integer.

Step-2. Induction step :

Assume that the proposition `P(n)` is true for `n = r, r+ 1, r + 2, .... , m`.

Step-3. Generalization step :

Prove that the proposition `P(n)` is true for `n =m +1`. Thus, if true, we generalize the result by saying that since the proposition is true for ` n = M + 1`, then it must also be true for `n = r, r + 1, r + 2, ....... , m` as assumed in Step `2`. Thus, the proposition is true for all `n ge r` belonging to the set of natural numbers.