Principle of Mathematical Induction

• Principle of Mathematical Induction and Simple Applications.

(i) The statement is true for n = 1, i.e., P(1) is true, and 
(ii) If the statement is true for n = k (where k is some positive integer), then the statement is also true for n = k + 1, i.e., truth of P(k) implies the truth of P (k + 1).
 Then, P(n) is true for all natural numbers n. 
Property (i) is simply  a statement of fact. There may be situations when a statement is true for all n ≥ 4. In this case, step 1 will start from n = 4 and we shall verify the result for n = 4, i.e., P(4). Suppose there is a given statement P(n)  involving the natural number n such that 

Property (ii) is a conditional property. It does not assert that the given statement is true for n = k, but only that if it is true for n = k, then it is also true for n = k +1. So, to prove that the  property holds , only prove that conditional proposition: 
If the statement is true for n = k, then it is also true for n = k + 1. 
This is sometimes referred to as the inductive step. The assumption that the given statement is true for n = k in this inductive step is called the inductive hypothesis. 
For example, frequently in mathematics, a formula will be discovered that appears to fit a pattern like 
`1 = 1^2 =1`
 `4 = 2^2 = 1 + 3` 
`9 = 3^2 = 1 + 3 + 5` 
`16 = 4^2 = 1 + 3 + 5 + 7`, etc. 
It is worth to be noted that the sum of the first two odd natural numbers is the square of second natural number, sum of the first three odd natural numbers is the square of third natural number and so on.Thus, from this pattern it appears that 
`1 + 3 + 5 + 7 + ... + (2"n" – 1) = "n"^2`, i.e, 
the sum of the first n odd natural numbers is the square of n. 
Let us write 
`"P"("n"): 1 + 3 + 5 + 7 + ... + (2"n" – 1) = "n"^2`.  We wish to prove that P(n) is true for all n. 
The first step in a proof that uses mathematical induction is to prove that P (1) is true. This step is called the basic step. Obviously 
`1 = 1^2`, i.e., P(1) is true. 
The next step is called the inductive step. Here, we suppose that P (k) is true for some positive integer k and we need to prove that P (k + 1) is true. Since P (k) is true, we have 
`1 + 3 + 5 + 7 + ... + (2k – 1) = k^2` ... (1) 
Consider
`1 + 3 + 5 + 7 + ... + (2k – 1) + {2(k +1) – 1}` ... (2) 
=` k^2 + (2k + 1) = (k + 1)^2` [Using (1)]
Therefore, P (k + 1) is true and the inductive proof is now completed. Hence P(n) is true for all natural numbers n.