NCERT Exemplar: Principle of Mathematical Induction | Mathematics (Maths) Class 11 - Commerce PDF Download

Q.1. Give an example of a statement P(n) which is true for all n ≥ 4 but P(1), P(2) and P(3) are not true. Justify your answer.
Ans.
The required statement is P(n) = 2n < n!
Justification: P(n) : 2n < n!
P(1) : 2.1 < 1!
⇒ 2 < 1 not true
P(2) : 2.2 < 2!
⇒ 4 < 2.1
⇒ 4 < 2 not true
P(3) : 2.3 < 3!
⇒ 6 < 3.2.1
⇒ 6 < 6 not true
P(4) : 2.4 < 4!
⇒ 8 < 4.3.2.1
⇒ 8 < 24 True
P(5) : 2.5 < 5!
⇒ 10 < 5.4.3.2.1
⇒ 10 < 120 True
Hence, P(n) = 2n < n! is not true for P(1), P(2) and P(3) but it is true for all values of n ≥ 4.

Q.2. Give an example of a statement P(n) which is true for all n. Justify your answer.
Prove each of the statements in Exercises 3 - 16 by the Principle of Mathematical Induction :
Ans. 
The required statement is
P(n) : 1 + 2 + 3 + ... + n =
Justification: P(1) :    
P(k) : 1 + 2 + 3 + ... + k = Let it be true.
P(k + 1) : 1 + 2 + 3 + ... + k + (k + 1)

Hence, P(k + 1) is true whenever P(k) is true.
Therefore by the principle of mathematical induction we have p(n) is true for all n.

Q.3.  4ⁿ – 1 is divisible by 3, for each natural number n.
Ans. 
Let P(n) : 4ⁿ – 1
Step 1: P(1) = 4 – 1 = 3 which is divisible by 3, so it is true.
Step 2: P(2) = 4^k – 1 = 3λ . Let it be true.
Step 3: P(k + 1)  =  4^k + 1 – 1
= 4^k .4 – 1 = 4.4^k –  4 + 3 = 4(4^k – 1) + 3
= 4 (3λ)  +  3 (from Step 2)
= 3[4λ + 1] which is true as it is divisible by 3.
Hence, P(k + 1) is true whenever P(k) is true.

Q.4. 2³ⁿ – 1 is divisible by 7, for all natural numbers n.
Ans. 
Let P(n) : 2³ⁿ – 1
Step 1: P(1) = 2^3.1 – 1 = 8 – 1 = 7 which is divisible by 7.
So, P(1) is true.
Step 2: P(k) = 2^3k – 1 = 7l. Let it be true.
Step 3: P(k + 1) =  2^3(k + 1) – 1
= 2^3k + 3 – 1 = 2³.2^3k –  8 + 7 = 8.2^3k – 8 + 7
= 8(2^3k – 1) + 7  (from Step 2)
= 8.7λ + 7
= 7(8λ + 1) which is true as it is divisible by 7
Hence, P(k + 1) is true whenever P(k) is true.

Q.5. n³ – 7n + 3 is divisible by 3, for all natural numbers n.
Ans. 
Let P(n) : n³ – 7n + 3
Step 1: P(1) : (1)³ – 7(1) + 3
= 1 – 7 + 3 = - 3  which is divisible by 3.
So, P(1) is true    .
Step 2: Assume P(k) is true for some  K∈N P(k) : k³ – 7k + 3 = 3λ, λ∈N.
⇒ k³ = 3λ + 7k – 3..............(i)
Step 3: Now we have to prove P(k + 1) : (k + 1)³ – 7(k + 1) + 3 is divisible by 3.
Now P(k + 1) : (k + 1)³ – 7(k + 1) + 3= k³ + 1 + 3k² + 3k – 7k – 7 + 3
= k³ + 3k² – 4k – 3
= (3λ + 7k – 3) + 3k² – 4k – 3 (using equation (i))
= 3k² + 3k + 3λ – 6
= 3(k² + k + λ – 2) is divisible by 3.
⇒ P(k + 1) is true.
Hence, P(k + 1) is true whenever P(k) is true.
Therefore by the principle of mathematical induction we have p(n) is true for all n.

Q.6. 3²ⁿ – 1 is divisible by 8, for all natural numbers n.
Ans. 
Let P(n) : 3²ⁿ – 1
Step 1: P(1) : 3² – 1 = 9 – 1 = 8 which is divisible by 8.
So, P(1) is true.
Step 2: Assume P(k) is true for some P(k) : 3^2k – 1 = 8λ, λ∈N.     Step 3: Now we have to prove P(k + 1) : 3^2(k + 1) – 1  is divisible by 8.
P(k + 1) : 3^2(k + 1) – 1
= 3^2k + 2 – 1 = 3².3^2k –  9 + 8 = 9(3^2k  – 1) + 8
= 9.8λ + 8 (from Step 2)
= 8[9λ + 1] is divisible by 8.
⇒ P(k + 1) is true.
Hence, P(k + 1) is true whenever P(k) is true.
Therefore by the principle of mathematical induction we have p(n) is true for all n.

Q.7. For any natural number n, 7ⁿ – 2ⁿ is divisible by 5.
Ans. 
Let P(n) : 7ⁿ – 2ⁿ
Step 1: P(1) : 7¹ – 2¹ = 5 which is divisible by 5.
So it is true for P(1).
Step 2: P(k) : 7^k – 2^k = 5λ. Let it be true for P(k).
Step 3: P(k +1) = 7^{k + 1} – 2^{k + 1}
= 7^{k + 1} + 7^k.2 – 7^k.2 – 2^{k + 1}
= (7^{k + 1} – 7^k.2) + 7^k.2 – 2^{k + 1})
= 7^k(7 – 2) + 2.(7^k – 2^k)
= 5.7^k + 2.5λ (from Step 2)
= 5(7^k + 2λ) which is divisible by 5.
So, it is true for P(k + 1).
Hence, P(k + 1) is true whenever P(k) is true.

Q.8. For any natural number n, xⁿ – yⁿ is divisible by x – y, where x and y are any integers with x ≠ y.
Ans. 
Let P(n) : xⁿ – yⁿ
Step 1: P(1) : x¹ – y¹ = x – y which is divisible by x – y.
So P(1) is true.
Step 2: P(k) : x^k – y^k = (x – y)λ. Let it be true.
Step 3: P(k + 1) = x^{k + 1} – y^k + 1 = x^{k + 1} – x^ky – x^ky – y^{k + 1}
= (x^k + 1 – x^ky) + (x^ky – y^k + 1)
= x^k(x – y) + y(x^k – y^k)
= x^k (x – y) + y.(x – y)λ (from Step 2)
= (x – y) (x^k + yλ)which is divisible by (x – y).
So, it is true for P(k + 1).

Q.9. n³ – n is divisible by 6, for each natural number n ≥ 2.
Ans. 
Let P(n) : n³ – n
Step 1: P(2) : 2³ – 2 = 6 which is divisible by 6. So it is true for P(2).
Step 2: P(k) : k³ – k = 6λ. Let it be true for k ≥ 2
⇒ k³ = 6λ + k ...(i)
Step 3: P(k + 1)
= (k + 1)³ – (k + 1)
= k³ + 1 + 3k² + 3k – k – 1
= k³ – k + 3(k² + k)
= 6λ + 3(k² + k) [from (i)]
We know that 3(k² + k) is divisible by 6 for every value of k ∈ N.
Hence P(k + 1) is true whenever P(k) is true.

Q.10. n (n² + 5) is divisible by 6, for each natural number n.
Ans. 
Let P(n) : n(n² + 5)
Step 1: P(1) : 1(1 + 5) = 6 which is divisible by 6. So it is true for P(1).
Step 2: P(k) : k(k² + 5) = 6λ. Let it be true
⇒ k³ + 5k = 6λ
⇒ k³ = 6λ – 5k ...(i)
Step 3: P(k + 1) = (k + 1)[(k + 1)² + 5]
= (k + 1)[k² + 1 + 2k + 5]
= (k + 1)[k2 + 2k + 6]
= k³ + 2k² + 6k + k² + 2k + 6
= k³ + 3k² + 8k + 6
= k³ + 5k + 3k² + 3k + 6
= 6λ – 5k + 5k + 3(k² + k + 2)  [From (i)]
= 6λ + 3(k² + k + 2)
We know that k² + k + 2 is divisible by 2 for each value of k ∈ N,
so, let k² + k + 2 = 2m.
So P(k + 1)  =  6λ +  3.2m = 6(λ + m) which is divisible by 6.
Hence, P(k + 1) is  true whenever P(k) is true.

Q.11. n² < 2ⁿ for all natural numbers n ≥ 5.
Ans.
Let P(n) : n² < 2ⁿ for all natural number, n ≥ 5.
Step 1: P(5) : 5² < 2⁵ ⇒ 25 < 32 which is true. So P(5) is true.
Step 2: Assume P(k) is true for some k∈N, k ≥ 5 ⇒ P(k) : k² < 2^k.............(i) is true.
Step 3: Now we have to prove P(k + 1) : (k + 1)² < 2^k + 1 is true where k ≥ 5.
Now we have (k + 1)²  = k² + 2k + 1 < 2^k + 2k + 1 .............(ii) [using equation(i)]
Now let 2^k + 2k + 1 < 2^k + 1
⇒ 2^k + 2k + 1 < 2^k . 2 =  2^k + 2^k
⇒ (2k + 1) < 2^k  which is true for K∈N , k ≥ 5 ….........(iii)
So (k + 1)2 < 2k + 2k   [using (ii) and (iii)]
⇒ (k + 1)2 < 2.2k
⇒(k + 1)2 < 2k + 1.
⇒ P(k + 1) is true.
Hence, P(k + 1) is true whenever P(k) is  true.
Therefore by the principle of mathematical induction we have p(n) is true for all n ≥ 5.

Q.12. 2n < (n + 2)! for all natural number n
Ans.
Let p(n) : 2n < (n + 2)! for all natural number n.
Step 1: P(1): 2.1 < (1 + 2)!
⇒ 2 < 3! ⇒ 2 < 6 which is true  (∴ 3! = 3 × 2 × 1 = 6)
So P(1) is true.
Step 2: Assume P(k) is true for some K∈N ⇒ P(k): 2k < (k + 2)! is true..
Step 3: Now we have to prove P(k + 1) : 2(k + 1) <  (k + 1 + 2)! is true.
Since 2k < (k + 2)! (from Step 2)
⇒ 2k + 2 < (k + 2)! + 2
⇒ 2(k + 1) < (k + 2)! + 2............(i)
Now let  (k + 2)! + 2 < (k + 3)!............(ii)
⇒ 2 < (k + 3)! - (k + 2)!
⇒2 <  (k + 2)! [k + 3-1]
2 < (k + 2)!.(k + 2) which is true for any natural number k.
∴ 2(k + 1) < (k + 3)!   [using (i) and (ii)]
⇒ 2(k + 1) < (k + 2 + 1)!
⇒ P(k + 1) is true.
Hence, P(k + 1) is true whenever P(k) is true.     Therefore by the principle of mathematical induction we have p(n) is true for all n.

Q.13. for all natural numbers n ≥ 2.
Ans. 
Let P(n)    
Step 1: P(2) :which is true.
Step 2: P(k)     Let it be true.
Step 3: P(k + 1) :
From Step 2, we have

⇒
⇒
Now if
⇒
⇒ ...(ii)
From eqn. (i) and (ii) we get

Hence, P(k +1) is true whenever P(k) is true.

Q.14. 2 + 4 + 6 + ... + 2n = n² + n for all natural numbers n.
Ans. 
 Let P(n) :  2 + 4 + 6 + ... + 2n = n² + n, ∀n ∈ N
Step 1: P(1) : 2 = 1² + 1 = 2
which is true for P(1)
Step 2: P(k) : 2 + 4 + 6 + ...+ 2k = k² + k. Let it be true.
Step 3: P(k + 1) : 2 +  4 + 6 +...+ 2k + 2k + 2
= k² + k + 2k + 2
= k² + 3k + 2
= k² + 2k + k + 1 + 1
= (k + 1)² + (k + 1)
Which is true for P(k + 1)
So, P(k + 1) is true whenever P(k) is true.

Q.15. 1 + 2 + 2² + ... + 2n = 2ⁿ⁺¹ – 1 for all natural numbers n.
Ans.
Let P(n) : 1 + 2 +  2² + … + 2ⁿ = 2^n + 1 – 1, n∈N.
P(n) : 2⁰ + 2¹ + 2² + … + 2n = 2ⁿ⁺¹ – 1
Step 1: P(1) L.H.S = 2⁰ +2¹ = 1 + 2 = 3. 
R.H.S = 2^1 + 1 – 1 = 2² – 1 = 4 – 1 = 3 .
L.H.S = R.H.S. So P(1) is true.
Step 2: Assume P(k) is true for some k∈N 
⇒ P(k) : 2⁰ + 2¹ + 2² + … + 2k = 2^k + 1 – 1..........(i)
Step 3: Now we have to prove P(k + 1) : 2⁰ + 2¹ + 2² +…+ 2^k + 2^k + 1 = 2^{(k + 1) + 1} – 1.
Adding 2k + 1 on both sides of equation (i)
2⁰ + 2¹ + 2² + … + 2^k + 2^k + 1
= 2^k + 1 – 1 + 2^k + 1 = 2.2^k + 1 – 1
= 2^k + 2 – 1
= 2^{(k + 1) + 1} – 1
⇒ P(k + 1) is true.

Q.16. 1 + 5 + 9 + ... + (4n – 3) = n (2n – 1) for all natural numbers n.
Ans. 
Let P(n) : 1 +  5  +  9 + … + (4n – 3) = n(2n – 1), ∀ n ∈ N
Step 1: P(1) : 1 = 1(2.1 – 1) = 1 which is true for P(1)
Step 2: P(k) : 1 + 5 + 9 +...+ (4k – 3) = k(2k – 1). Let it be true.
Step 3: P(k + 1) : 1 + 5 + 9 +...+ (4k – 3) + (4k + 1)
= k(2k – 1) + (4k + 1) = 2k2 – k + 4k + 1
= 2k2 + 3k + 1 = 2k2 + 2k + k + 1
= 2k(k + 1) + 1(k + 1) = (2k + 1)(k + 1)
= (k + 1)(2k + 2 – 1) = (k + 1) [2(k + 1) – 1]
Which is true for P(k + 1).
Hence, P(k + 1) is true whenever P(k) is true.

Long Answer Type
Q.17. A sequence a₁, a₂, a₃ ... is defined by letting a₁ = 3 and a_k = 7a_k–1 for all natural numbers k ≥ 2. Show that a_n = 3.7^n–1 for all natural numbers.
Ans. 
Given that:
a₁ = 3
a₂ = 7a_{2 – 1} = 7.a₁ = 7.3 = 21
a₃ = 7.a₃ – 1 = 7.a₂ = 7.21 = 147...
Let P(n) : a_n = 3.7^n – 1, ∀n∈N
Step 1: P(2): a₂ = 3.7^2 – 1 = 21 ⇒ 21. So P(2) is true.
Step 2: P(k): a_k = 3.7_{k – 1}. Let it be true.
Step 3: a_k = 7a_{k – 1} (given)
Put k = k + 1
a_k + 1 = 7a_k = 7(3.7^{k – 1}) = 3.7^{k + 1 – 1} = 3.7^{(k + 1) – 1}
which is true for P(k + 1)
Hence, P(k + 1) is true whenever P(k) is true.

Q.18. A sequence b₀, b₁, b₂ ... is defined by letting b₀ = 5 and b_k = 4 + b_{k – 1} for all natural numbers k. Show that b_n = 5 + 4n for all natural number n using mathematical induction.
Ans. 
We have b₀ = 5 and b_k = 4 + b_{k – 1}
⇒b₀ = 5, b₁ = 4 + b₀ = 4 + 5 = 9 and b₂ = 4 + b₁ = 4 + 9 = 13
Let P(n) : b_n = 5 + 4_n
Step 1: P(1) :  b₁ = 5 + 4 = 9 ⇒ 9 = 9 which is true.
Step 2: Assume P(k) is true for some k∈N ⇒ P(k): bk = 5 + 4k is true..  
Step 3: Given that:
 P(k) = 4 + b_{k – 1}
⇒ P(k + 1) = 4 + b_{k + 1 – 1}
⇒ P(k + 1) = 4 + b_k = 4 + 5 + 4k
⇒ P(k + 1) = 5 + 4(k + 1) which is true for P(k + 1)
Hence, P(k + 1) is true whenever P(k) is true.

Q.19. A sequence d1, d2, d3 ... is defined by letting d1 = 2 and dk =
for all natural numbers, k ≥ 2. Show that dn =for all n ∈ N.
Ans. 
Given that: d₁ = 2 and d_k =
Let P(n) :
Step 1: P(1) :which is true for P(1).
Step 2: P(k) :Let it be true for P(k).
Step 3: Given that: d_k =
∴ 
⇒
⇒ Which is true for P(k + 1)
Hence, P(k + 1) is true whenever P(k) is true.

Q.20. Prove that for all  n ∈ N
cos α + cos (α + β) + cos (α + 2β) + ... + cos (α + (n – 1) β)

Ans.
Let P(n) : cos a + cos (a + b) + cos (a + 2b) + ... + cos [a + (n – 1)b]

Step 1: P(1) :cos α =
which is true for P(1)
Step 2: P(k) : cos α + cos (α +β) + cos (α + 2β) + ... + cos [α + (k – 1)β]
Let it be true.
Step 3: P(k + 1) : cos α + cos (α + b) + cos (α + 2b) + ... + cos [α + (k – 1)b]
+ cos [ α + (k + 1 – 1)b]

(from Step 2)

[∴ 2 cos A sin B = sin (A + B) – sin (A – B)]


which is true for P(k + 1)
Hence, P(k + 1) is true whenever P(k) is true.

Q.21. Prove that, cos θ cos 2θ cos2²θ ... cos2^n–1θfor all n ∈ N.
Ans. 
Let P(n) : cos θ.cos 2θ.cos 2²θ…cos 2^{n – 1}θ    ,∀n ∈ N.
Step 1: P(1) :
⇒ cos θ = cos θ which is true for P(1)
Step 2: P(k) : cos θ.cos 2θ.cos 2²θ ... cos 2^{k – 1} θ =
Let it be true for P(k).
Step 3: P(k + 1) : cos θ.cos 2θ.cos 2²θ ... cos 2^{k – 1}θ. cos 2^{(k + 1) – 1}θ


    [∵ 2 sin θ cos θ = sin 2θ]
which is true for P(k + 1).
Hence, P(k + 1) is true whenever P(k) is true.

Q.22. Prove that, sin θ + sin 2θ + sin 3θ + ... + sin nθ 
 for all n ∈ N.
Ans.
Let p(n) : sin θ + sin 2θ + sin 3θ + … + sin nθ   
 
Step 1: P(1) : sin θ =
∴ sin θ = sin θ which is true for P(1).
Step 2: P(k) : sin θ + sin 2θ + sin 3θ + ... + sin kθ
. Let it be true for P(k).
Step 3: P(k + 1) : sin θ + sin 2θ + sin 3θ + ... + sin (k + 1)θ





which is true for P(k + 1).
Hence, P(k + 1) is true whenever P(k) is true.

Q.23. Show thatis a natural number for all n ∈ N.
Ans.
Let P(n)  :
Step 1: P(1)  :    
Which is true for P(1).
Step 2: P(k) . Let it be true for P(k) and let
=λ
Step 3: P(k + 1) =



= λ + k⁴ + 2k³ + 3k² + 2k + 1     [from Step 2]
= positive integers = natural number
Which is true for P(k + 1).
Hence, P(k + 1) is true whenever P(k) is true.

Q.24. Prove that, for all natural numbers  n > 1.
Ans.
 Let P(n) :    
Step 1: P(2) :
which is true for P(2).
Step 2: P(k) :.Let it be true for P(k).
Step 3: P(k + 1) :
Since 

Which is true for P(k + 1).
Hence, P(k + 1) is true whenever P(k) is true.

Q.25. Prove that number of subsets of a set containing n distinct elements is
 2ⁿ, for all n ∈ N.
Ans. 
Let P(n) : Number of subsets of a set containing n distinct
elements is 2ⁿ, ∀ n ∈ N
Step 1: It is clear that P(1) is true for n = 1. Number of subsets 
= 2¹ = 2. Which is true.
Step 2: P(k) is assumed to be true for n = k. Since the number of subsets = 2^k.
Step 3: P(k + 1) =  2^k + 1
We know that if one number (i.e., element) is added to the elements of a given set, 
the number of subsets become double.
∴ Number of subsets of set having (k + 1) distinct elements
= 2 x 2k = 2k +  1 which is true for P(k + 1).
Hence P(k + 1) is true
whenever P(k) is true.

Objective Type Questions
Q.26. If 10ⁿ + 3.4ⁿ⁺² + k is divisible by 9 for all n ∈ N,
then the least positive integral value of k is
(A) 5
(B) 3
(C) 7
(D) 1
Ans. 
Let P(n) = 10ⁿ + 3.4^{n + 2} + k is divisible by 9, ∀ n ∈ N
P(1) = 10¹ +  3.4^1 + 2 + k = 10 + 3.64 + k
= 10 + 192 + k = 202 + k must be divisible by 9.
If (202 + k) is divisible by 9 then k must be equal to 5
202 + 5 = 207 which is divisible by 9

So, the least positive integral value of k = 5.
Hence, the correct option is (a).

Q.27. For all n ∈ N, 3.5²ⁿ⁺¹ + 2³ⁿ⁺¹ is divisible by
(A) 19
(B) 17
(C) 23
(D) 25
Ans.
Let P(n) : 3.5^2n + 1 + 2^3n + 1
For P(1) : 3.5^2.1 + 1 + 2^{3.1 + 1} = 3.53 + 24 = 3(125) + 16 = 375 + 16
= 391 = 23 x 17
So it is divisible by 17 and 23 both.
Hence, the correct option is (b) and (c).

Q.28. If xⁿ – 1 is divisible by x – k, then the least positive integral value of k is (A) 1
(B) 2
(C) 3
(D) 4
Ans. 
Let P(n) = xⁿ – 1 is divisible by x – k.
P(1) = x – 1 is divisible by x – k.
Since k = 1 is the possible least integral value of k.
Hence, the correct option is (a).

Fill in the Blanks
Q.29. If P(n) : 2n < n!, n ∈ N, then P(n) is true for all n ≥ ________.
Ans.
Given that P(n) : 2n < n!, ∀ n ∈ N
For n = 1 , 2 < 1 (Not true)
For n = 2 , 2 × 2 < 2! ⇒ 4 < 2  (Not true) For n  = 3 , 2 × 3 < 3! ⇒ 6 < 3.2.1 ⇒ 6 < 6 (Not true) For  n = 4 , 2 × 4 < 4! ⇒ 8 < 4.3.2.1 ⇒ 8 < 24 (true)
For n = 5 , 2 × 5 < 5! ⇒ 10 < 5.4.3.2.1 ⇒10 < 120(true)
So, P(n) is true for n ≥ 4.
Hence, the value of the filler  is 4.

State whether the following statement is true or false. Justify.
Q.30. Let P(n) be a statement and let P(k) ⇒ P(k + 1), for some natural number k, then P(n) is true for all n ∈ N.
Ans.
Given that: P(k) ⇒ P(k + 1)
P(1)⇒ P(2) which is not true.
Hence, the statement is ‘False’.