Chapter 4.1 Overview Mathematical induction is one of the techniques which can be used to prove variety of mathematical statements which are formulated in terms of n, where n is a positive integer. 4.1.1 The principle of mathematical induction Let P(n) be a given statement involving the natural number n such that (i) The statement is true for n = 1, i.e., P(1) is true (or true for any fixed natural number) and (ii) If the statement is true for n = k (where k is a particular but arbitrary natural number), 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. 4.2 Solved Examples Short Answer Type Prove statements in Examples 1 to 5, by using the Principle of Mathematical Induction for all n ∈ N, that : Example 1 1 + 3 + 5 + ... + (2n – 1) = n2 Solution Let the given statement P(n) be defined as P(n) : 1 + 3 + 5 +...+ (2n – 1) = n2, for n ∈ N. Note that P(1) is true, since P(1) : 1 = 12 Assume that P(k) is true for some k ∈ N, i.e., P(k) : 1 + 3 + 5 + ... + (2k – 1) = k 2 Now, to prove that P(k + 1) is true, we have 1 + 3 + 5 + ... + (2k – 1) + (2k + 1) = k2 + (2k + 1) (Why?) = k2 + 2k + 1 = (k + 1)2 Thus, P(k+ 1) is true, whenever P(k) is true. Hence, by the Principle of Mathematical Induction, P(n) is true for all n∈ N. n−1( −1) ( n+1) nnExample 2 ∑tt(1) , for all natural numbers n≥ 2.+= t=13 Solution Let the given statement P(n), be given as n−1( −1) ( n+1) nnP( ): n ∑( += , for all natural numbers n≥ 2.tt 1) t=13 We observe that 21− 1 1.2.3 P(2): ∑tt(1) + = ∑tt( +1) = 1.2 = t=1 t=13 2.(2 −1) ( 2 +1) = 3 Thus, P(n) in true for n= 2. Assume that P(n) is true for n= k∈ N. −1( −1) ( k+1) k kk i.e., P(ktt(1) =) : ∑+ t=13 To prove that P(k+ 1) is true, we have k(11) k+− ∑tt(1) + = ∑tt(+1) t=1 t=1 k−1 (1)(1) kk− k+ = ∑tt(1) kk +1) +kk++( = (1) + t=13 ⎡−+k 13⎤ kk(1)( + k+2) (1) =kk= +⎢ ⎥⎣ 3 ⎦ 3 (k+1)(( k+− k 1) 1) 1) 1))(( ++ = 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≥ 2. ⎛ 1 ⎞⎛ 1 ⎞⎛ 1 ⎞n+1Example 3 1− .1 − ... 1−= , for all natural numbers, n≥ 2.⎜ 2 ⎟⎜ 2 ⎟⎜ 2 ⎟⎝ 2 ⎠⎝ 3 ⎠⎝ n⎠ 2n Solution Let the given statement be P(n), i.e., ⎛ 1 ⎞⎛ 1 ⎞⎛ 1 ⎞ n+1 P(n) : 1− .1 − ... 1−= , for all natural numbers, n≥ 2⎜ 2 ⎟⎜ 2 ⎟⎜ 2 ⎟⎝ 2 ⎠⎝ 3 ⎠⎝ n⎠ 2n We, observe that P (2) is true, since ⎛ 1 ⎞ 1 41− 3 21+ 1−=1− ==⎜ 2 ⎟ = 2 4 442 ×2⎝⎠Assume that P(n) is true for some k∈ N, i.e., ⎛ 1 ⎞⎛ 1 ⎞⎛ 1 ⎞k+11− .1− ... 1−=P(k) : ⎜ 2 ⎟⎜ 2 ⎟⎜ 2 ⎟⎝ 2 ⎠⎝ 3 ⎠⎝ k⎠ 2k Now, to prove that P (k+ 1) is true, we have ⎛ 1 ⎞⎛ 1 ⎞⎛ 1 ⎞⎛ 1 ⎞1− .1− ... 1− .1−⎜ 2 ⎟⎜ 2 ⎟⎜ 2 ⎟⎜ 2 ⎟⎝ 2 ⎠⎝ 3 ⎠⎝ k⎠⎝ (k+1) ⎠ k+1⎛ 1 ⎞ k2 +2k (k++1) 1 =⎜1 − 2 ⎟= = 2k (k+1) 2( +1) 2(k+kk 1) ⎝⎠ 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≥ 2. Example 4 22n– 1 is divisible by 3. Solution Let the statement P(n) given as P(n) : 22n– 1 is divisible by 3, for every natural number n. We observe that P(1) is true, since 22 – 1 = 4 – 1 = 3.1 is divisible by 3. Assume that P(n) is true for some natural number k, i.e., P(k): 22k–1 is divisible by 3, i.e., 22k– 1 = 3q, where q∈ N Now, to prove that P(k+ 1) is true, we have P(k+ 1) : 22(k+1) – 1 = 22k+ 2 – 1 = 22k. 22 – 1 =22k. 4 – 1 = 3.22k + (22k– 1) = 3.22k + 3q =3 (22k + q) = 3m, where m ∈ N 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. Example 5 2n + 1 < 2n, for all natual numbers n ≥ 3. Solution Let P(n) be the given statement, i.e., P(n) : (2n + 1) < 2n for all natural numbers, n ≥ 3. We observe that P(3) is true, since 2.3 + 1 = 7 < 8 = 23 Assume that P(n) is true for some natural number k, i.e., 2k + 1 < 2k To prove P(k + 1) is true, we have to show that 2(k + 1) + 1 < 2k+1. Now, we have 2(k + 1) + 1 = 2 k + 3 =2k + 1 + 2 < 2k + 2 < 2k . 2 = 2k + 1. 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 ≥ 3. Long Answer Type Example 6 Define the sequence a1, a2, a3... as follows : a = 2, a = 5 a , for all natural numbers n ≥ 2.1nn–1 (i) Write the first four terms of the sequence. (ii) Use the Principle of Mathematical Induction to show that the terms of the sequence satisfy the formula an = 2.5n–1 for all natural numbers. Solution (i) We have a = 21a2 = 5a2–1 = 5a1 = 5.2 = 10 a3 = 5a3–1 = 5a2 = 5.10 = 50 a = 5a = 5a = 5.50 = 25044–13(ii) Let P(n) be the statement, i.e., P(n) : a = 2.5 n–1 for all natural numbers. We observe that P(1) is true nAssume that P(n) is true for some natural number k, i.e., P(k) : ak = 2.5k – 1. Now to prove that P (k + 1) is true, we have P(k + 1) : a k + 1 =5.ak = 5 . (2.5k – 1) = 2.5k = 2.5(k + 1)–1 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. Example 7 The distributive law from algebra says that for all real numbers c, a1 and a2, we have c (a1 + a2) = ca1 + ca2. Use this law and mathematical induction to prove that, for all natural numbers, n ≥ 2, if c,a1, a2, ...,an are any real numbers, then c (a + a + ... + a ) = ca + ca + ... + ca12n 12n Solution Let P(n) be the given statement, i.e., P(n) : c (a1 + a2 + ... + an) = ca1 + ca2 + ... can for all natural numbers n ≥ 2, for c, a1, a2, ... an ∈ R. We observe that P(2) is true since c(a + a) = ca + ca(by distributive law)1212 Assume that P(n) is true for some natural number k, where k > 2, i.e., P(k) : c (a1 + a2 + ... + ak) = ca1 + ca2 + ... + cak Now to prove P(k + 1) is true, we have P(k + 1) : c (a + a + ... + a + a)12kk + 1= c ((a + a + ... + a) + a)12kk + 1= c (a1 + a2 + ... + ak) + cak + 1 (by distributive law) = ca1 + ca2 + ... + cak + cak + 1 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 ≥ 2. Example 8 Prove by induction that for all natural number n sin α + sin (α + β) + sin (α + 2β)+ ... + sin (α + (n – 1) β) n −1 ⎛⎞ nβsin ( α+ β)sin ⎜⎟22⎝⎠ = β⎛⎞sin ⎜⎟2⎝⎠ Solution Consider P (n) : sin α + sin (α + β) + sin (α + 2β) + ... + sin (α + (n – 1) β) n −1 ⎛nβ⎞sin ( α+ β)sin ⎜⎟2 ⎝ 2 ⎠ = , for all natural number n.β⎛⎞sin ⎜⎟2⎝⎠ We observe that P (1) is true, since βsin ( α+0)sin 2P (1) : sin α = βsin 2 Assume that P(n) is true for some natural numbers k, i.e., P (k) : sin α + sin (α + β) + sin (α + 2β) + ... + sin (α + (k – 1)β) k −1 ⎛kβ⎞sin ( α+ β)sin ⎜⎟2 ⎝ 2 ⎠ = β⎛⎞sin ⎜⎟2⎝⎠ Now, to prove that P (k + 1) is true, we have P (k + 1) : sin α + sin (α + β) + sin (α + 2β) + ... + sin (α + (k – 1) β) + sin (α + kβ) k −1 ⎛kβ⎞sin ( α+ β)sin 2 ⎝⎜ 2 ⎠⎟ += sin ( α+ kβ)β⎛⎞sin ⎜⎟2⎝⎠ ⎛ k −1 ⎞ kββsin ⎜α+ β⎟sin +sin (α+ β )sin k ⎝ 2 ⎠ 22 = βsin 2 ⎛β⎞⎛ β⎞⎛ β⎞⎛ β⎞kk α+ β+ cos α− −cos α+β− +cos α+β− −cos k⎜⎟⎜⎟⎜ ⎟⎜ ⎟⎝ 2 ⎠⎝ 2 ⎠⎝ 2 ⎠⎝ 2 ⎠ = β2sin 2 ⎛β⎞⎛ β⎞ cos α− −cos α+ β+ k⎜⎟⎜ ⎟⎝ 2 ⎠⎝ 2 ⎠= β2sin 2 ⎛ kβ⎞ ⎛kβ+β⎞sin ⎜α+ sin ⎟⎜ ⎟⎝ 2 ⎠⎝ 2 ⎠ = βsin 2 ⎛ kβ⎞ ⎛β⎞sin α+ sin ( k +1) ⎜⎟ ⎜⎟⎝ 2 ⎠⎝ 2 ⎠ = βsin 2 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 number n. Example 9 Prove by the Principle of Mathematical Induction that 1× 1! + 2 × 2! + 3 × 3! + ... + n × n!= (n + 1)! – 1 for all natural numbers n. Solution Let P(n) be the given statement, that is, P(n) : 1 × 1! + 2 × 2! + 3 × 3! + ... + n × n!= (n + 1)! – 1 for all natural numbers n. Note that P (1) is true, since P (1) : 1× 1! =1 = 2 – 1 = 2! – 1. Assume that P(n) is true for some natural number k, i.e., P(k) : 1 × 1! + 2 × 2! + 3 × 3! + ... + k × k! = (k + 1)! – 1 To prove P(k + 1) is true, we have P (k + 1) : 1× 1! + 2 ×2! + 3 × 3! + ... + k × k!+ (k + 1) × (k + 1)! = (k +1)! – 1 + (k + 1)! × (k + 1) =(k + 1 + 1) (k + 1)! – 1 =(k + 2) (k +1)! – 1 = ((k + 2)! – 1 Thus P (k + 1) is true, whenever P (k) is true. Therefore, by the Principle of Mathematical Induction, P (n) is true for all natural number n. Example 10 Show by the Principle of Mathematical Induction that the sum S of the nn term of the series 12 + 2 × 22 + 32 + 2 × 42 + 52 + 2 × 62 ... is given by ⎧nn( +1) 2 ⎪,if nis even ⎪2Sn = ⎨2( +1) ⎪nn ,if nis odd ⎪⎩ 2 ⎧nn( +1) 2 ⎪, when nis even ⎪2Solution Here P(n) : Sn = ⎨ ⎪2( +nn 1) , when nis odd ⎪⎩ 2 Also, note that any term T of the series is given byn⎧n2 if nis odd ⎪T = n⎨22if nis even ⎪n⎩ We observe that P(1) is true since 21.2 1.(1 1) P(1) : S =12 = 1 = =+ 122 Assume that P(k) is true for some natural number k, i.e. Case 1 When kis odd, then k + 1 is even. We have P (k+ 1) : Sk+ 1 =12 + 2 × 22 + ... + k2 + 2 × (k + 1)2 2(kk+1) = + 2 × (k+ 1)2 2 (k+1) (k+1) = [k2 + 4(k+ 1)] (as kis odd, 12 + 2 × 22 + ... + k2 = k2)22 k+1 =[k2 + 4k+ 4]2 +1 [( 1) 1] 2kk++ = 2(k+2) 2= (k +1) 2 So P(k+ 1) is true, whenever P(k) is true in the case when kis odd. Case 2 When kis even, then k+ 1 is odd. Now, P(k+ 1) : 12 + 2 × 22 + ... + 2.k2 + (k+ 1)2 kk+1)22( (k+1) = + (k+ 1)2 (as kis even, 12 + 2 × 22 + ... + 2k2 = k )22 2)2(k+1(k+2) (k+1) (( k+1) +1) == 22 Therefore, P (k+ 1) is true, whenever P (k) is true for the case when kis even. Thus P (k+ 1) is true whenever P (k) is true for any natural numbers k. Hence, P (n) true for all natural numbers. Objective Type Questions Choose the correct answer in Examples 11 and 12 (M.C.Q.) Example 11 Let P(n) : “2n< (1 × 2 × 3 × ... × n)”. Then the smallest positive integer for which P (n) is true is (A) 1 (B)2 (C)3 (D) 4 Solution Answer is D, since P (1) : 2 < 1 is false P (2) : 22 < 1 × 2 is false P (3) : 23 < 1 × 2 × 3 is false But P (4) :24 < 1 × 2 × 3 × 4 is true Example 12 A student was asked to prove a statement P (n) by induction. He proved that P (k+ 1) is true whenever P (k) is true for all k> 5 ∈ N and also that P (5) is true. On the basis of this he could conclude that P (n) is true (A) for all n∈ N (B) for all n> 5 (C) for all n≥ 5 (D) for all n< 5 Solution Answer is (C), since P(5) is true and P(k + 1) is true, whenever P (k) is true. Fill in the blanks in Example 13 and 14. Example 13 If P (n) : “2.42 n+ 1 + 33n+1 is divisible by λ for all n∈ N” is true, then the value of λ is ____ Solution Now, for n= 1, 2.42+1 + 33+1 =2.43 + 34= 2.64 + 81 = 128 + 81 = 209, for n = 2, 2.45 + 37 = 8.256 + 2187 = 2048 + 2187 = 4235 Note that the H.C.F. of 209 and 4235 is 11. So 2.42n+1 + 33n+1 is divisible by 11. Hence, λ is 11 Example 14 If P (n) : “49n + 16n+ kis divisible by 64 for n∈ N” is true, then the least negative integral value of kis ______. Solution For n= 1, P(1) : 65 + kis divisible by 64. Thus k, should be – 1 since, 65 – 1 = 64 is divisible by 64. Example 15 State whether the following proof (by mathematical induction) is true or false for the statement. ( + 1)(2 n+ 1) nnP(n): 12 + 22 + ... + n2 = 6 Proof By the Principle of Mathematical induction, P(n) is true for n= 1, 1(1 +1)(2 1 +1) kk+1) (2 k+1) ⋅ (12 = 1 = .Again for some k≥ 1, k2 = . Now we6 6 prove that (k+1)(( k+ 1) +1)(2( k+ 1) +1) (k+ 1)2 = 6 Solution False Since in the inductive step both the inductive hypothesis and what is to be proved are wrong. Short Answer Type 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. 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 : 3. 4n – 1 is divisible by 3, for each natural number n. 4. 23 n– 1 is divisible by 7, for all natural numbers n. 5. n3 – 7n+ 3 is divisible by 3, for all natural numbers n. 6. 32 n– 1 is divisible by 8, for all natural numbers n. 7. For any natural number n, 7n – 2n is divisible by 5. 8. For any natural number n, xn – yn is divisible by x – y, where x and y are any integers with x ≠ y. 9. n3 – n is divisible by 6, for each natural number n ≥ 2. 10. n (n2 + 5) is divisible by 6, for each natural number n. 11. n2 < 2n for all natural numbers n ≥ 5. 12. 2n < (n + 2)! for all natural number n. 1 1 1< + +... +13. n , for all natural numbers n ≥ 2.1 2 n 14. 2 + 4 + 6 + ... + 2n = n2 + n for all natural numbers n. 15. 1 + 2 + 22 + ... + 2n = 2n+1 – 1 for all natural numbers n. 16. 1 + 5 + 9 + ... + (4n – 3) = n (2n – 1) for all natural numbers n. Long Answer Type Use the Principle of Mathematical Induction in the following Exercises. 17. A sequence a, a, a ... is defined by letting a = 3 and a = 7a for all natural123 1kk–1numbers k ≥ 2. Show that a = 3.7n–1 for all natural numbers. n18. A sequence b0, b1, b ... is defined by letting b = 5 and b= 4 + b for all2 0k k – 1natural numbers k. Show that bn = 5 + 4n for all natural number n using mathematical induction. dk−119. A sequence d1, d2, d ... is defined by letting d = 2 and d = for all natural3 1kk2 numbers, k ≥ 2. Show that d = for all n ∈ N. nn!20. Prove that for all n ∈ N cos α + cos (α + β) + cos (α + 2β) + ... + cos (α + (n – 1) β) ⎛ ⎛ n −1 ⎞⎞ ⎛ nβ⎞ cos α+ β sin ⎜ ⎜ ⎟⎟⎜⎟⎝ ⎝ 2 ⎠⎠ ⎝ 2 ⎠ = βsin 2 nsin 2 θ21. Prove that, cos θ cos 2θ cos22θ ... cos2n–1 θ = n , for all n ∈ N.2sin θ sin n θ(n +1)sin θ 22=22. Prove that, sinθ + sin 2θ + sin 3θ + ... + sinnθ , for alln ∈ N.θsin 2 n5 n37n23. Show that ++ is a natural number for all n ∈ N.5 315 1 1 113 24. Prove that ++...+> , for all natural numbers n > 1. n +1 n + 22n 24 25. Prove that number of subsets of a set containing n distinct elements is 2n , for all n ∈ N. Objective Type Questions Choose the correct answers in Exercises 26 to 30 (M.C.Q.). 26. If 10n + 3.4n+2 + 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 27. For all n ∈ N, 3.52n+1 + 23n +1 is divisible by (A) 19 (B) 17 (C) 23 (D) 25 28. If xn – 1is divisible by x – k, then the least positive integral value of k is (A) 1 (B) 2 (C) 3 (D) 4 Fill in the blanks in the following : 29. If P(n) : 2n < n!, n ∈ N, then P(n) is true for all n ≥ ________. State whether the following statement is true or false. Justify. 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.