TOPICS

Unit-4(Examples)

Principle of Mathematical Induction

**Example-1 :-** For all n ≥ 1, prove that :

**Example-2 :-** Prove that 2^{n} > n for all positive integers n.

Let P(n): 2^{n}> n When n = 1, 2^{1}>1. Hence P(1) is true. Assume that P(k) is true for any positive integer k, i.e., 2^{k}> k ... (1) We shall now prove that P(k+1) is true whenever P(k) is true. Multiplying both sides of (1) by 2, we get 2. 2^{k}> 2k i.e., 2^{k+1}> 2k = k + k > k + 1 Therefore, P(k + 1) is true when P(k) is true. Hence, by principle of mathematical induction, P(n) is true for every positive integer n.

**Example-3 :-** For all n ≥ 1, prove that :

**Example-4 :-** For every positive integer n, prove that 7^{n} – 3^{n} is divisible by 4.

We can write P(n) : 7^{n}– 3^{n}is divisible by 4. We note that P(1): 7^{1}– 3^{1}= 4 which is divisible by 4. Thus P(n) is true for n = 1 Let P(k) be true for some natural number k, i.e., P(k) : 7^{k}– 3^{k}is divisible by 4. We can write 7^{k}– 3^{k}= 4d, where d ∈ N. Now, we wish to prove that P(k + 1) is true whenever P(k) is true. Now 7^{k+1}– 3^{k+1}= 7^{k+1}– 7.3^{k}+ 7.3^{k}– 3^{k+1}= 7(7^{k}– 3^{k}) + (7 – 3)3^{k}= 7(4d) + (7 – 3)3^{k}= 7(4d) + 4.3^{k}= 4(7d + 3^{k}) From the last line, we see that 7^{k+1}– 3^{k+1}is divisible by 4. Thus, P(k + 1) is true when P(k) is true. Therefore, by principle of mathematical induction the statement is true for every positive integer n.

**Example-5 :-** Prove that : (1 + x)^{n} ≥ (1 + nx), for all natural number n, where x > – 1.

Let P(n) be the given statement, i.e., P(n): (1 + x)^{n}≥ (1 + nx), for x > – 1. We note that P(n) is true when n = 1, since ( 1+x) ≥ (1 + x) for x > –1 Assume that P(k): (1 + x)^{k}≥ (1 + kx), x > – 1 is true. ... (1) We want to prove that P(k + 1) is true for x > –1 whenever P(k) is true. ... (2) Consider the identity (1 + x)^{k+1}= (1 + x)^{k}(1 + x) Given that x > –1, so (1+x) > 0. Therefore , by using (1 + x)^{k}≥ (1 + kx), we have (1 + x)^{k+1}≥ (1 + kx)(1 + x) i.e. (1 + x)^{k+1}≥ (1 + x + kx + kx^{2}). ... (3) Here k is a natural number and x^{2}≥ 0 so that kx^{2}≥ 0. Therefore (1 + x + kx + kxsup>2) ≥ (1 + x + kx), and so we obtain (1 + x)^{k+1}≥ (1 + x + kx) i.e. (1 + x)^{k+1}≥ [1 + (1 + k)x] Thus, the statement in (2) is established. Hence, by the principle of mathematical induction, P(n) is true for all natural numbers.

**Example-6 :-** Prove that : 2.7^{n} + 3.5^{n} – 5 is divisible by 24, for all n ∈ N.

Let the statement P(n) be defined as P(n) : 2.7^{n}+ 3.5^{n}– 5 is divisible by 24. We note that P(n) is true for n = 1, since 2.7 + 3.5 – 5 = 24, which is divisible by 24. Assume that P(k) is true i.e. 2.7^{k}+ 3.5^{k}– 5 = 24q, when q ∈ N ... (1) Now, we wish to prove that P(k + 1) is true whenever P(k) is true. We have 2.7^{k+1}+ 3.5^{k+1}– 5 = 2.7^{k}. 7^{1}+ 3.5^{k}. 5^{1}– 5 = 7 [2.7^{k}+ 3.5^{k}– 5 – 3.5^{k}+ 5] + 3.5^{k}. 5 – 5 = 7 [24q – 3.5^{k}+ 5] + 15.5^{k}–5 = 7 × 24q – 21.5^{k}+ 35 + 15.5^{k}– 5 = 7 × 24q – 6.5^{k}+ 30 = 7 × 24q – 6 (5^{k}– 5) = 7 × 24q – 6 (4p) [(5^{k}– 5) is a multiple of 4] = 7 × 24q – 24p = 24 (7q – p) = 24 × r; r = 7q – p, is some natural number. ... (2) The expression on the R.H.S. of (1) is divisible by 24. Thus P(k + 1) is true whenever P(k) is true. Hence, by principle of mathematical induction, P(n) is true for all n ∈ N.

**Example-7 :-** Prove that : 1^{2} + 2^{2} + ... + n^{2} > n^{3}/3, n ∈ N

Let P(n) be the given statement. i.e., 1^{2}+ 2^{2}+ ... + n^{2}> n^{3}/3, n ∈ N We note that P(n) is true for n = 1 since 1^{2}> 1^{3}/3 Assume that P(k) is true i.e. P(k) : 1^{2}+ 2^{2}+ ... + k^{2}> k^{3}/3 ...(1) We shall now prove that P(k + 1) is true whenever P(k) is true. We have 1^{2}+ 2^{2}+ 3^{2}+ ... + k^{2}+ (k + 1)^{2}= (1^{2}+ 2^{2}+ 3^{2}+ ... + k^{2}) + (k + 1)^{2}> k^{3}/3 + (k + 1)^{2}[by (1)] = 1/3 [k^{3}+ 3k^{2}+ 6k + 3] = 1/3 [(k + 1)^{3}+ 3k + 2] > 1/3 (k+1)^{3}Therefore, P(k + 1) is also true whenever P(k) is true. Hence, by mathematical induction P(n) is true for all n ∈ N.

**Example-8 :-** Prove the rule of exponents (ab)^{n} = a^{n}b^{n} by using principle of mathematical induction for every natural number.

Let P(n) be the given statement i.e. P(n) : (ab)^{n}= a^{n}b^{n}. We note that P(n) is true for n = 1 since (ab)^{1}= a^{1}b^{1}. Let P(k) be true, i.e., (ab)^{k}= a^{k}b^{k}... (1) We shall now prove that P(k + 1) is true whenever P(k) is true. Now, we have (ab)^{k+1}= (ab)^{k}(ab) = (a^{k}b^{k}) (ab) [by (1)] = (a^{k}. a^{1}) (b^{k}. b^{1}) = a^{k+1}. b^{k+1}Therefore, P(k + 1) is also true whenever P(k) is true. Hence, by principle of mathematical induction, P(n) is true for all n ∈ N.

CLASSES