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.