The Principle of Mathematical Induction
Deduction : Generalization of Specific Instance o Example : Rohit is a man & All men eat food à Rohit eats food .
o Example : Mukesh is an Engg & All Engg earn good money à Mukesh earn good money .
o Example : Sun is a star & All stars have their own light à Sun has its own light .
Induction : Specific Instances à Generalization
o Rohit eats food . Vikash eats food . Rohit and Vikash are men à All men eat food
o Statement is true for n = 1 , n = k & n = k + 1 à Statement is true for all .
For a statement P ( n ) involving the natural number n , if
� P ( 1 ) is true � 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 .
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 . This is sometimes referred to as inductive step . The assumption that the given statement is true for n = k in this inductive step is called the inductive hypothesis .
Example : Prove that 2 n > n for all positive integers n Solution : Let P ( n ): 2 n > n Step 1 : When n = 1 , 2 1 > 1 . Hence P ( 1 ) is true . Step 2 : Assume that P ( k ) is true for any positive integer k , i . e ., 2 k > k ... ( 1 ) Step 3 : We shall now prove that P ( k + 1 ) is true whenever P ( k ) is true .