Chapter 4 – Principle Of Mathematical Induction

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

t (t + 1) = , for all natural numbers n ≥ 2. t =1 3 Solution Let the given statement P(n), be given as n −1 n ( n − 1) ( n + 1) P( n) : t (t + 1) = , for all natural numbers n ≥ 2. t =1 3 We observe that 2−1 1 1.2.3 P(2): t (t + 1) = t (t + 1) = 1.2 = t =1 t =1 3 2.(2 − 1) (2 + 1) = Thus, P(n) in true for n = 2. Assume that P(n) is true for n = k ∈ N. k −1 k ( k − 1) ( k + 1) i.e., P(k) : t (t + 1) = t =1 3 To prove that P(k + 1) is true, we have ( k +1−1) k t (t + 1) = t (t +1) t =1 t =1 k −1 k (k −1)(k +1) = t (t +1) + k (k +1) = + k (k +1) t =1 3 k −1 + 3 k (k +1)(k + 2) = k (k +1) = 3 3 (k +1)((k +1) −1)) ((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 n ≥ 2. PRINCIPLE OF MATHEMATICAL INDUCTION 63 1 1 1 n +1

1− 2 . 1− 2 ... 1− 2 = , for all natural numbers, n ≥ 2.

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.

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.

Define the sequence a1, a2, a3... as follows : a1 = 2, an = 5 an–1, for all natural numbers n ≥ 2.

• (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 a1 = 2 a2 = 5a2–1 = 5a1 = 5.2 = 10 a3 = 5a3–1 = 5a2 = 5.10 = 50 a4 = 5a4–1 = 5a3 = 5.50 = 250 (ii) Let P(n) be the statement, i.e., P(n) : an = 2.5 n–1 for all natural numbers. We observe that P(1) is true Assume 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 PRINCIPLE OF MATHEMATICAL INDUCTION 65 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.

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 (a1 + a2 + ... + an) = ca1 + ca2 + ... + can 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(a1 + a2) = ca1 + ca2 (by distributive law) 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 (a1 + a2 + ... + ak + ak + 1) = c ((a1 + a2 + ... + ak) + ak + 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.

Prove by induction that for all natural number n sin α + sin (α + β) + sin (α + 2β)+ ... + sin (α + (n – 1) β) n −1 nβ sin (α + β)sin 2 2 = β Solution Consider P (n) : sin α + sin (α + β) + sin (α + 2β) + ... + sin (α + (n – 1) β) n −1 nβ sin (α + β)sin 2 2 = , for all natural number n. β We observe that P (1) is true, since β sin (α + 0)sin P (1) : sin α = β 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 = β 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β) β k −1 kβ β sin α + β sin + sin ( α + k β ) sin 2 2 2 = β β β β β cos α − − cos α + k β − + cos α + k β − − cos α + kβ + 2 2 2 2 = β 2sin PRINCIPLE OF MATHEMATICAL INDUCTION 67 β β cos α − − cos α + k β + 2 2 = β 2sin kβ kβ +β sin α + sin 2 2 = β kβ β sin α + sin (k + 1) 2 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.

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.

Show by the Principle of Mathematical Induction that the sum Sn of the n term of the series 12 + 2 × 22 + 32 + 2 × 42 + 52 + 2 × 62 ... is given by n(n + 1) 2 , if n is even Sn = n 2 ( n + 1) , if n is odd n (n +1) 2 , when n is even Solution Here P(n) : Sn = n 2 (n +1) , when n is odd Also, note that any term Tn of the series is given by n 2 if n is odd Tn = 2n 2 if n is even We observe that P(1) is true since 1.2 12.(1 + 1) P(1) : S1 = 12 = 1 = = 2 2 Assume that P(k) is true for some natural number k, i.e. Case 1 When k is odd, then k + 1 is even. We have P (k + 1) : Sk + 1 = 12 + 2 × 22 + ... + k2 + 2 × (k + 1)2 k 2 ( k + 1) = + 2 × (k + 1)2 (k + 1) 2 (k + 1) = [k + 4(k + 1)] (as k is odd, 12 + 2 × 22 + ... + k2 = k2 ) 2 2 k +1 2 = [k + 4k + 4] k +1 [(k + 1) + 1]2 = (k + 2) 2 = (k + 1) 2 2 So P(k + 1) is true, whenever P(k) is true in the case when k is odd. Case 2 When k is even, then k + 1 is odd. PRINCIPLE OF MATHEMATICAL INDUCTION 69 Now, P (k + 1) : 12 + 2 × 22 + ... + 2.k2 + (k + 1)2 k ( k +1) ( k + 1) 2 = + (k + 1)2 (as k is even, 12 + 2 × 22 + ... + 2k2 = k ) 2 2 ( k +1) (k + 2) (k +1) 2 ((k +1) +1) = = 2 2 Therefore, P (k + 1) is true, whenever P (k) is true for the case when k is 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.

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

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.

If P (n) : “2.42n + 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

If P (n) : “49n + 16n + k is divisible by 64 for n ∈ N” is true, then the least negative integral value of k is ______. Solution For n = 1, P(1) : 65 + k is divisible by 64. Thus k, should be – 1 since, 65 – 1 = 64 is divisible by 64.

State whether the following proof (by mathematical induction) is true or false for the statement. n(n + 1) (2n + 1) P(n): 12 + 22 + ... + n2 = Proof By the Principle of Mathematical induction, P(n) is true for n = 1, 1(1 + 1) (2 ⋅ 1 + 1) k (k + 1) (2k + 1)