Principal of Mathematical Induction

Problem Exercises

1) Let P (n): n² + n is even. Is P (1) true?

Solution:

Given, P (n): n² + n is even

At n = 1,

P (1) = 1² + 1 = 1 + 1 = 2, which is even

Hence, P (1) is true.

2) Let P (n): n(n + 1)(n + 2) is divisible by 3. What is P(3)?

Solution:

Given, P (n) : n(n + 1)(n + 2) is divisible by 3.

At n = 3,

P (3) = 3(3+1) (3+2) = 345 = 60, which is divisible by 3.

Hence, P (3) = 60.

3) Let P (n): n² > 9. Is P (2) true?

Solution:

Given, P (n): n² > 9

At n = 2,

P (2) = 2² = 4, which is lesser than 9.

Hence, P (2) is false.

4) Give an example of a statement such that P(3) is true but P(4) is not true.

Solution:

The required statement

P (n): n³ + n is divisible by 3 …. (i)

Justification:

Put n = 3 in (i)

P (3): 3³ + 3 = 27 + 3 = 30, which is divisible by 3.

Put n = 4 in (i)

P (4): 4³ + 4 = 64 + 4 = 68, which is divisible by 3.

5) If P (n): 1 + 4 + 7 + … + (3n – 2) = n (3n – 1). Verify P(n) for n = 1,2

Solution:

Given, P (n): 1 + 4 + 7 + … + (3n-2) = n (3n-1)

Therefore,

P (1): 1 = .1. (3.1-1) or 1 = 1

P (2): 1 + 4 = .2. (3.2-1) or 5 = 5 Hence, verified.

6) If P (n) is the statement “n² - n + 41 is prime.” Prove that P (1) and P (2) are true but P (41) is not true.

Solution.

We have, P (n): n² - n + 41 is prime

P (1): 1² - 1 + 41 = 41 is prime

P (2): 2² - 2 + 41 = 43 is prime

P (3): 3² - 3 + 41 = 47 is prime

Thus, P (1), P (2) and P (3) are true.

P (41): (41)² - 41 + 41 = (41)² is not prime

Therefore, P (41) is not true.

7) Prove the following by using principle of mathematical induction? n ϵ M.3²ⁿ when divided by 8 leaves the remainder 1.

Solution.

Let P (n): 3²ⁿ when divided by 8, the remainder is 1.

Or

P (n) = 3²ⁿ = 8λ + 1 for some λ ϵ M

Step 1:

P (1): 3² = 8λ + 1 for some λ ϵ M

Therefore, 3² = 8 x 1 + 1 = 8λ + 1, where λ = 1

Therefore, P (1) is true.

Step 2:

Let P (m) be true.

Then,

32m = 8λ + 1 for some λ ϵ M …. (i)

Step 3:

We shall show that P (m+1) is true for which we have to show that 3^2(m+1) when divided by 8, the remainder is 1,

i.e. 3^2(m+1) = 8λ + 1 for some M ϵ N.

Now, 3^2(m+1) = 3^2m.3² = (8λ + 1).9 [from (i)]

= 72λ + 9 = 72λ + 8 + 1 = 8(9λ + 1) + 1,

Where r = 9λ + 1 ϵ N

ð P(m+1) is true whenever P(m) is true. Hence by principle of mathematical induction P(n) is true for all n ϵ n.

8) Prove the following by using principle of mathematical induction? n ϵ M. 4ⁿ + 15n – 1 is divisible by 9.

Solution:

Let P (n): 4ⁿ + 15n – 1 is divisible by 9.

Step 1:

P (1); 4ⁿ + 15 x 1 – 1 = 18, which is divisible by 9

Thus, P (1) is true.

Step 2:

Let P (k) be true. Then, 4^k + 15k – 1 is divisible by 9.

ð 4^k + 15k – 1 = 9λ, for some λ ϵ M. ….(i)

Step 3:

We shall now show that P (k + 1) is true for this we have to show that is divisible by 9.

Now, 4^{k + 1} + 15(k + 1) – 1

= 4^k. 4 + 15(k + 1) – 1

= (9λ – 15k + 1) .4 + 15(k + 1) – 1 [from (i)]

= 36λ – 45k + 18

= 9(4λ – 5k + 2), which is divisible by 9.

Therefore, P (k + 1) is true.

Thus,

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

Hence, by principle of mathematical induction P (n) is true for all n ϵ M.

9) 2n + 1 < 2ⁿ, for all natural numbers n ≥ 3.

Solution.

Let P (n) be the given statement,

i.e., P (n): (2n + 1) < 2ⁿ for all natural numbers, n ≥ 3.

We observe that P (3) is true, since

2.3 + 1 = 7 < 8 = 2³

Assume that P (n) is true for some natural number k, i.e., 2k + 1 <2^k

To prove P (k + 1) is true, we have to show that 2(k + 1) + 1 < 2^{k + 1}

Now, we have

2(k + 1) + 1 = 2k + 3

= 2k + 1 + 2 < 2^k + 2 < 2^k. 2 = 2^{k + 1}

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

Hence, by the principle of mathematical induction P (n) is false for all natural numbers n ≥ 3.

10)Prove the following by principle of mathematical induction Ɐn ϵ M. n < 2ⁿ

Solution.

Let P (n): n < 2ⁿ

Step 1:

P (1): 1 < 2¹ or 1 < 2

Therefore, P (1) is true.

Step 2:

Let P (k) be true for some k ϵ N, i.e., p(k) : k < 2^k

Step 3:

We shall prove that P (k + 1) is true wherever P (k) is true.

For this we have to prove that (k + 1) > 2^{(k + 1)}

Now, P (k) is true.

K < 2^k

2k < 2.2^k

ð 2k < 2^{k + 1}

ð (k + k) < 2^{k + 1}

k + 1 ≤ k + k < 2^{k + 1}

[If 1 ≤ m, then m + 1 ≤ m + m]

k + 1 < 2^{k + 1}

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

Hence, by principle of mathematical induction P (n) is true for all n ϵ N.

11) Prove the following by principle of mathematical induction? n ϵ M. (1 + x)ⁿ ≥ 1 + nx

Solution:

Let P (n): (1 + x) ⁿ ≥ 1 + nx

Step 1:

P (1): (1 + x) ¹ ≥ 1 + x

Therefore P (1) is true.

Step 2:

Let P (k) be true, then

(1 + x) ^k ≥ 1 + kx

Step 3:

We shall prove that P (k + 1) is true whenever P (k) is true.

For this we have to prove that (1 + x) ^{k + 1} ≥ 1 + (k + 1) x

Now, P (k) is true.

(1 + x) ^k ≥ 1 + kx

Multiplying both sides by (1 + x)

(1 + x) (1 + x) ^k ≥ (1 + x) (1 + kx)

(1 + x) ^{k + 1} ≥ 1 + (k + 1) x + kx²

(1 + x) ^{k + 1} ≥ (k + 1) x + kx² ≥ 1 + (k + 1) x [since, kx² ≥ 0]

(1 + x) ^{k + 1} ≥ 1 + (k + 1) x

P (k + 1) is true.

Hence, by principle of mathematical induction, P (n) is true for all n ϵ N.