Mathematical Induction

Mathematical Induction

Introduction

The process of deducing particular results from a general result is called deduction. The process of establishing a valid general result from particular results is called induction. The

principle of mathematical induction is used to establish the validity of a general result involving natural numbers.

Consider the statement:

P(n) : ''n(n + 1) is even''. We wish to show that this statement is true for all n N.

For n = 1, P(1) = 1 × 2 = 2 (even)

For n = 2, P(2) = 2 × 3 = 6 (even) and so on.

Alternatively, we can prove by stating that for n even, n(n + 1) is even and for n odd, n + 1 is even and thus n(n + 1) is even. But all statement may not be that simple. e.g.

.

For n = 1, P(1) : 3 > 1 is true.

If we assume that the result is true for n = r, then P(r) : 3^r > r is true.

For n = r + 1, P(r + 1) : 3^r+1 = 3^r × 3 > 3^r > r+1& for r N.

Hence P(r + 1) is true.


Principle of Mathematical Induction

Let P(n), n N be a statement such that

(i) P(1) is true, and (ii) truth of P(r) the truth of P(r + 1).

Then by the principle of mathematical induction, the statement is true for all n N. Mathematical induction involves the following steps:

(a) Firstly, we prove that the result is true for n = 1 (or any other permissible minimum integral value of n),

(b) then, we assume that the result is true for n = r,

(c) finally, we prove that the result is true for n = r + 1.

From this, we conclude by the principle of mathematical induction that the result (or the statement) is true for all n N.