Class 11 – Mathematics – Chapter 4 – Principle Mathematical Induction

Q1. Give an example of a statement P(n) which is true for all nâ‰¥ 4 but P(l), P(2) and P(3) are not true. Justify your answer.

Sol. Consider the statement P(n): 3n < n!

For n = 1, 3 x 1 < 1!, which is not true
For n = 2, 3 x 2 < 2!, which is not true
For n = 3, 3 x 3 < 3!, which is not true
For n = 4, 3 x 4 < 4!, which is true
For n = 5, 3 x 5 < 5!, which is true

Q2. Give an example of a statement P(n) which is true for all Justify your answer. Instruction for Exercises 3-16: Prove each of the statements in these Exercises by the Principle of Mathematical Induction.

Q3. 4n – 1 is divisible by 3, for each natural number
Sol: Let P(n): 4n – 1 is divisible by 3 for each natural number n.
Now, P(l): 41 – 1 = 3, which is divisible by 3 Hence, P(l) is true.
Let us assume that P(n) is true for some natural number n = k.
P(k): 4k – 1 is divisible by 3
or                             4k – 1 = 3m, mâˆˆ N  (i)
Now, we have to prove that P(k + 1) is true.
P(k+ 1): 4k+1 – 1
= 4k-4-l
= 4(3m + 1) â€“ 1  [Using (i)]
= 12 m + 3
= 3(4m + 1), which is divisible by 3 Thus, P(k + 1) is true whenever P(k) is true.
Hence, by the principle of mathematical induction P(n) is true for all natural numbers n.

Q4. 23n – 1 is divisible by 7, for all natural numbers
Sol: Let P(n): 23n – 1 is divisible by 7
Now, P( 1): 23 â€” 1 = 7, which is divisible by 7.
Hence, P(l) is true.
Let us assume that P(n) is true for some natural number n = k.
P(k): 23k – 1 is divisible by 7.
or                             23k -1 = 7m, mâˆˆ N  (i)
Now, we have to prove that P(k + 1) is true.
P(k+ 1): 23(k+1)– 1
= 23k.23– 1
= 8(7 m + 1) – 1
= 56 m + 7
= 7(8m + 1), which is divisible by 7.
Thus, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for all natural numbers n.

Q5. n3 – 7n + 3 is divisible by 3, for all natural numbers
Sol: Let P(n): n3 – 7n + 3 is divisible by 3, for all natural numbers n.
Now P(l): (l)3 – 7(1) + 3 = -3, which is divisible by 3.
Hence, P(l) is true.
Let us assume that P(n) is true for some natural number n = k.
P(k) = K3 – 7k + 3 is divisible by 3
or K3 â€“ 7k + 3 = 3m, mâˆˆ N         (i)
Now, we have to prove that P(k + 1) is true.
P(k+ 1 ):(k + l)3 – 7(k + 1) + 3
= k3 + 1 + 3k(k + 1) â€“ 7kâ€” 7 + 3 = k3 -7k + 3 + 3k(k + l)-6
= 3m + 3[k(k+l)-2]  [Using (i)]
= 3[m + (k(k + 1) – 2)], which is divisible by 3 Thus, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for all natural numbers n.

Q6. 32n – 1 is divisible by 8, for all natural numbers
Sol: Let P(n): 32n – 1 is divisible by 8, for all natural numbers n.
Now, P(l): 32 – 1 = 8, which is divisible by 8.
Hence, P(l) is true.
Let us assume that, P(n) is true for some natural number n = k.
P(k): 32k – 1 is divisible by 8
or                             32k -1 = 8m, m âˆˆ N  (i)
Now, we have to prove that P(k + 1) is true.
P(k+ 1): 32(k+1)– l
= 32k • 32 â€” 1
= 9(8m + 1) – 1     (using (i))
= 72m + 9 – 1
= 72m + 8
= 8(9m +1), which is divisible by 8 Thus P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for all natural numbers n.

Q7. For any natural number n, 7n â€“ 2n is divisible by 5.
Sol: Let P(n): 7n â€“ 2n is divisible by 5, for any natural number n.
Now, P(l) = 71-21 = 5, which is divisible by 5.
Hence, P(l) is true.
Let us assume that, P(n) is true for some natural number n = k.

.’.  P(k) = 7k -2k is divisible by 5
or  7k – 2k = 5m, mâˆˆ N                                                                                                                                                     (i)
Now, we have to prove that P(k + 1) is true.
P(k+ 1): 7k+1 -2k+1
= 7k-7-2k-2
= (5 + 2)7k -2k-2
= 5.7k + 2.7k-2-2k
= 5.7k + 2(7k – 2k)
= 5 • 7k + 2(5 m)     (using (i))
= 5(7k + 2m), which divisible by 5.
Thus, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for all natural numbers n.

Q8. For any natural number n, xn -yn is divisible by x -y, where x and y are any integers with x â‰ y
Sol:
Let P(n) : xn – yn is divisible by x – y, where x and y are any integers with xâ‰ y.
Now, P(l): x1 -y1 = x-y, which is divisible by (x-y)
Hence, P(l) is true.
Let us assume that, P(n) is true for some natural number n = k.
P(k): xk -yk is divisible by (x – y)
or   xk-yk = m(x-y),m âˆˆ N …(i)
Now, we have to prove that P(k + 1) is true.
P(k+l):xk+l-yk+l
= xk-x-xk-y + xk-y-yky
= xk(x-y) +y(xk-yk)
= xk(x – y) + ym(x – y)  (using (i))
= (x -y) [xk+ym], which is divisible by (x-y)
Hence, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for any natural number n.

Q9. n3 -n is divisible by 6, for each natural number nâ‰¥
Sol: Let P(n): n3 – n is divisible by 6, for each natural number n> 2.
Now, P(2): (2)3 -2 = 6, which is divisible by 6.
Hence, P(2) is true.
Let us assume that, P(n) is true for some natural number n = k.
P(k): k3 – k is divisible by 6
or    k3 -k= 6m, mâˆˆ N       (i)
Now, we have to prove that P(k + 1) is true.
P(k+ 1): (k+ l)3-(k+ 1)
= k3+ 1 +3k(k+ l)-(k+ 1)
= k3+ 1 +3k2 + 3k-k- 1 = (k3-k) + 3k(k+ 1)
= 6m + 3 k(k +1)  (using (i))
Above is divisible by 6.    (âˆ´ k(k + 1) is even)
Hence, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for any natural number n,nâ‰¥ 2.

Q10. n(n2 + 5) is divisible by 6, for each natural number
Sol: Let P(n): n(n2 + 5) is divisible by 6, for each natural number.
Now P(l): 1 (l2 + 5) = 6, which is divisible by 6.
Hence, P(l) is true.
Let us assume that P(n) is true for some natural number n = k.
P(k): k( k2 + 5) is divisible by 6.
or K (k2+ 5) = 6m, mâˆˆ N         (i)
Now, we have to prove that P(k + 1) is true.
P(K+l):(K+l)[(K+l)2 + 5]
= (K + l)[K2 + 2K+6]
= K3 + 3 K2 + 8K + 6
= (K2 + 5K) + 3 K2 + 3K + 6 =K(K2 + 5) + 3(K2 + K + 2)
= (6m) + 3(K2 + K + 2)        (using (i))
Now, K2 + K + 2 is always even if A is odd or even.
So, 3(K2 + K + 2) is divisible by 6 and hence, (6m) + 3(K2 + K + 2) is divisible by 6.
Hence, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for any natural number n.

Q11. n2 < 2n, for all natural numbers n â‰¥
Sol: Let P(n): n2 < 2n for all natural numbers nâ‰¥ 5.
Now P(5): 52 < 25  or 25 < 32, which is true.
Hence, P(5) is true.
Let us assume that P(n) is true for some natural number n = k.
âˆ´ P(k): k2 < 2k  (i)
Now, to prove that P(k + 1) is true, we have to show that P(k+ 1): (k+ l)2 <2k+1
Using (i), we get
(k + l)2 = k2 + 2k + 1 < 2k + 2k + 1         (ii)
Now let, 2k + 2k + 1 < 2k+1      (iii)
âˆ´ 2k + 2k + 1 < 2 • 2k
2k + 1 < 2k, which is true for all k > 5 Using (ii) and (iii), we get (k + l)2 < 2k+1 Hence, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for any natural number n,nâ‰¥ 5.

Q12. 2n<(n + 2)! for all natural numbers
Sol: Let P(n): 2n < (n + 2)! for all natural numbers n.
P( 1): 2 < (1 + 2)! or 2 < 3! or 2 < 6, which is true.
Hence,P(l) is true.
Let us assume that P(n) is true for some natural number n = k.
P(k) :2k<(k + 2)!  (i)
To prove that P(k + 1) is true, we have to show that
P(k + 1): 2(k+ 1) < (k + 1 + 2)!
or 2(k+ 1) < (k + 3)!
Using (i), we get
2(k + 1) = 2k + 2<(k+2) !  +2  (ii)
Now let, (k + 2)! + 2 < (k + 3)!  (iii)
=>  2 < (k+ 3)! – (k+2) !
=> 2 < (k + 2) ! [k+ 3-1]
=>2<(k+ 2) ! (k + 2), which is true for any natural number.
Using (ii) and (iii), we get 2(k + 1) < (k + 3)!
Hence, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for any natural number n.  Q14. 2 + 4 + 6+… + 2n = n2 + n, for all natural numbers
Sol: Let P(n) :2 + 4 + 6+ …+2 n = n2 + n
P(l): 2 = l2 + 1 = 2, which is true
Hence, P(l) is true.
Let us assume that P(n) is true for some natural number n = k.
âˆ´ P(k): 2 + 4 + 6 + .,.+2k = k2 + k  (i)
Now, we have to prove that P(k + 1) is true.
P(k + l):2 + 4 + 6 + 8+ …+2k+ 2 (k +1)
= k2 + k + 2(k+ 1)  [Using (i)]
= k2 + k + 2k + 2
= k2 + 2k+1+k+1
= (k + 1)2 + k+ 1
Hence, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for any natural number n.

Q15. 1 + 2 + 22 + … + 2n = 2n +1 – 1 for all natural numbers
Sol: Let P(n): 1 + 2 + 22 + … + 2n = 2n +1 – 1, for all natural numbers n
P(1): 1 =20 + 1 â€” 1 = 2 â€” 1 = 1, which is true.
Hence, ,P(1) is true.
Let us assume that P(n) is true for some natural number n = k.

P(k): l+2 + 22+…+2k = 2k+1-l              (i)

Now, we have to prove that P(k + 1) is true.

P(k+1): 1+2 + 22+ …+2k + 2k+1
= 2k +1 – 1 + 2k+1  [Using (i)]
= 2.2k+l– 1 = 1
= 2(k+1)+1-1
Hence, P(k + 1) is true whenever P(k) is true.
So, by the principle of mathematical induction P(n) is true for any natural number n.

Q16. 1 + 5 + 9 + … + (4n – 3) = n(2n – 1), for all natural numbers
Sol: Let P(n): 1 + 5 + 9 + … + (4n – 3) = n(2n – 1), for all natural numbers n.
P(1): 1 = 1(2 x 1 – 1) = 1, which is true.
Hence, P(l) is true.
Let us assume that P(n) is true for some natural number n = k.
âˆ´ P(k):l+5 + 9 +…+(4k-3) = k(2k-1)  (i)
Now, we have to prove that P(k + 1) is true.
P(k+ 1): 1 + 5 + 9 + … +  (4k- 3) + [4(k+ 1) – 3]
= 2k2 -k+4k+ 4-3
= 2k2 + 3k + 1
= (k+ 1)( 2k + 1)

= (k+l)[2(k+l)-l]

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

So, by the principle of mathematical induction P(n) is true for any natural number n.

Q17. A sequence ax, a2, a3, … is defined by letting a1=3 and ak = 7ak1 for all natural numbers kâ‰¥ Show that an = 3 • 7  n-1 for all natural numbers.
Sol: We have a sequence ax, a2, a3… defined by letting a, = 3 and ak = 7ak1, for all natural numbers kâ‰¥2. Q18. A sequence b0, b1, b2, … is defined by letting b0 = 5 and bk = 4 + bk1, for all natural numbers Show that bn = 5 + 4n, for all natural number n using mathematical induction.
Sol. We have a sequence b0, b1, b2,… defined by letting b0 = 5 and bk = 4 + bk1,, for all natural numbers k.                    So, by the principle of mathematical induction P(n) is true for any natural number rt,n> 1.

Q25. Prove that number of subsets of a set containing n distinct elements is 2?, for all n âˆˆ
Sol: Let P(n): Number of subset of a set containing n distinct elements is 2?, for all ne N.
For n = 1, consider set A = {1}. So, set of subsets is {{1}, âˆ…}, which contains 21 elements.
So, P(1) is true.
Let us assume that P(n) is true, for some natural number n = k.
P(k): Number of subsets of a set containing k distinct elements is 2k To prove that P(k + 1) is true,
we have to show that P(k + 1): Number of subsets of a set containing (k + 1) distinct elements is 2k+1
We know that, with the addition of one element in the set, the number of subsets become double.
Number of subsets of a set containing (k+ 1) distinct elements = 2×2k = 2k+1
So, P(k + 1) is true. Hence, P(n) is true.