 |
| Principle of Mathematical Induction |
 |
If P(n) is a statement (n N); such that: |
| |
|
|
| |
- truth of P(k) implies the truth of P(k+1), then by the principle of
|
| |
mathematical induction (P.M.I.), the statement P(n) is true for n N. |
| |
| |
| Step 1: Show that the result holds for n = 1. |
| |
| Step 2: Assume the validity of the result for n equal to some arbitrary but fixed natural number, say, k. |
| |
| Step 3: Show that the result holds for n = k+1. |
| |
| |
| |
| Step 4: Conclude that the result holds for all natural numbers. |
| |
| |
| For any natural number n, prove that |
| |
 |
| |
| Proof: |
| |
| We shall use PMI to prove that |
| |
|
| |
| Step 1: Let n = 1 |
| |
|
| |
 |
| |
(1) is true for n = 1. |
| |
| Step 2: Let (1) be true for n = k |
| |
…(2) |
| |
| Step 3: Let n = k + 1 |
| |
| LHS of (1) |
| |
 |
| |
| |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
R.H.S of (1) |
| |
| \ (1) is true for n = k + 1. |
| |
By P.M.I., we have |
| |
 |
| |