Mathematical Induction

Introduction

      The word 'Induction' means method of reasoning from individual cases to general ones or from observed instances to unobserved ones. Many important mathematical formulae are such that a result is formed by some means which does not provide for a direct proof. Mathematical Induction is a principle by which one can arrive at a conclusion about a statement for all positive integers, after proving certain related proposition.

Statement

     Some sentences depend on a variable for its truth value (i.e., true or false).

     e.g., "2+4+6+…2n=2n" is true for n=1 but false for n=2, n=3 etc.

     As the above sentence is definitely true or definitely false for a particular positive integral value of n, the sentence is a statement and it depends on nÎN for its truth-value. Such statements are called predicates and are symbolised as P(n).

Principle of Mathematical Induction (PMI)

     A statement P(n) is true for all nÎN if
(i) P(1) is true (ii) P(r) is true implies P(r+1) is true.

Illustrative Examples

     The following are the Illustrative Examples:
If P(n) is the statement n²-n+41 is prime, prove that P(1), P(2) are true but P(41) is not true.

     Prove by P.M.I , n < 2ⁿ for all nÎN

Summary

     1. A sentence is called a statement if it can be adjudged as true or false.

     2. Every statement is a sentence, but a sentence may or may not be a statement.

     3. A statement involving natural number n is generally denoted by P(n).

Conclusion

     Let n N and P(n) denote a certain statement or formula or theorem. Then P(n) holds good for every natural number n if

     (i) it holds for n = 1 and

     (ii) it holds for n = k+1 whenever it holds for n = k.