Chapter 4: Principle of Mathematical Induction

According to the question,

P(n) which is true for all n.

Let P(n) be,

⇒ P(k) is true for all k.

Therefore, P(n) is true for all n.

Prove each of the statements in Exercises 3 to 16 by the Principle of Mathematical Induction:

According to the question,

P(n) = 4ⁿ – 1 is divisible by 3.

So, substituting different values for n, we get,

P(0) = 4⁰ – 1 = 0 which is divisible by 3.

P(1) = 4¹ – 1 = 3 which is divisible by 3.

P(2) = 4² – 1 = 15 which is divisible by 3.

P(3) = 4³ – 1 = 63 which is divisible by 3.

Let P(k) = 4^k – 1 be divisible by 3,

So, we get,

⇒ 4^k – 1 = 3x.

Now, we also get that,

⇒  P(k+1) = 4^k+1 – 1

= 4(3x + 1) – 1

= 12x + 3 is divisible by 3.

⇒ P(k+1) is true when P(k) is true

Therefore, by Mathematical Induction,

P(n) = 4ⁿ – 1 is divisible by 3 is true for each natural number n.

According to the question,

P(n) = 2³ⁿ – 1 is divisible by 7.

So, substituting different values for n, we get,

P(0) = 2⁰ – 1 = 0 which is divisible by 7.

P(1) = 2³ – 1 = 7 which is divisible by 7.

P(2) = 2⁶ – 1 = 63 which is divisible by 7.

P(3) = 2⁹ – 1 = 512 which is divisible by 7.

Let P(k) = 2^3k – 1 be divisible by 7

So, we get,

⇒ 2^3k – 1 = 7x.

Now, we also get that,

⇒  P(k+1) = 2^3(k+1) – 1

= 2³(7x + 1) – 1

= 56x + 7

= 7(8x + 1) is divisible by 7.

⇒ P(k+1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = 2³ⁿ – 1 is divisible by7, for all natural numbers n.

According to the question,

P(n) = n³ – 7n + 3 is divisible by 3.

So, substituting different values for n, we get,

P(0) = 0³ – 7×0 + 3 = 3 which is divisible by 3.

P(1) = 1³ – 7×1 + 3 = −3 which is divisible by 3.

P(2) = 2³ – 7×2 + 3 = −3 which is divisible by 3.

P(3) = 3³ – 7×3 + 3 = 9 which is divisible by 3.

Let P(k) = k³ – 7k + 3 be divisible by 3

So, we get,

⇒ k³ – 7k + 3 = 3x.

Now, we also get that,

⇒  P(k+1) = (k+1)³ – 7(k+1) + 3

= k³ + 3k² + 3k + 1 – 7k – 7 + 3

= 3x + 3(k² + k – 2) is divisible by 3.

⇒ P(k+1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = n³ – 7n + 3 is divisible by 3, for all natural numbers n.

According to the question,

P(n) = 3²ⁿ – 1 is divisible by 8.

So, substituting different values for n, we get,

P(0) = 3⁰ – 1 = 0 which is divisible by 8.

P(1) = 3² – 1 = 8 which is divisible by 8.

P(2) = 3⁴ – 1 = 80 which is divisible by 8.

P(3) = 3⁶ – 1 = 728 which is divisible by 8.

Let P(k) = 3^2k – 1 be divisible by 8

So, we get,

⇒ 3^2k – 1 = 8x.

Now, we also get that,

⇒  P(k+1) = 3^2(k+1) – 1

= 3²(8x + 1) – 1

= 72x + 8 is divisible by 8.

⇒ P(k+1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = 3²ⁿ – 1 is divisible by 8, for all natural numbers n.

According to the question,

P(n) = 7ⁿ – 2ⁿ is divisible by 5.

So, substituting different values for n, we get,

P(0) = 7⁰ – 2⁰ = 0 Which is divisible by 5.

P(1) = 7¹ – 2¹ = 5 Which is divisible by 5.

P(2) = 7² – 2² = 45 Which is divisible by 5.

P(3) = 7³ – 2³ = 335 Which is divisible by 5.

Let P(k) = 7^k – 2^k be divisible by 5

So, we get,

⇒ 7^k – 2^k = 5x.

Now, we also get that,

⇒  P(k+1)= 7^k+1 – 2^k+1

= (5 + 2)7^k – 2(2^k)

= 5(7^k) + 2 (7^k – 2^k)

= 5(7^k) + 2 (5x) Which is divisible by 5.

⇒ P(k+1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = 7ⁿ – 2ⁿ is divisible by 5 is true for each natural number n.

According to the question,

P(n) = xⁿ – yⁿ is divisible by x – y, x integers with x ≠ y.

So, substituting different values for n, we get,

P(0) = x⁰ – y⁰ = 0 Which is divisible by x − y.

P(1) = x − y Which is divisible by x − y.

P(2) = x² – y²

= (x +y)(x−y) Which is divisible by x−y.

P(3) = x³ – y³

= (x−y)(x²+xy+y²) Which is divisible by x−y.

Let P(k) = x^k – y^k be divisible by x – y;

So, we get,

⇒ x^k – y^k = a(x−y).

Now, we also get that,

⇒  P(k+1) = x^k+1 – y^k+1

= x^k(x−y) + y(x^k−y^k)

= x^k(x−y) +y a(x−y) Which is divisible by x − y.

⇒ P(k+1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) xⁿ – yⁿ is divisible by x – y, where x integers with x ≠ y which is true for any natural number n.

According to the question,

P(n) = n³ – n is divisible by 6.

So, substituting different values for n, we get,

P(0) = 0³ – 0 = 0 Which is divisible by 6.

P(1) = 1³ – 1 = 0 Which is divisible by 6.

P(2) = 2³ – 2 = 6 Which is divisible by 6.

P(3) = 3³ – 3 = 24 Which is divisible by 6.

Let P(k) = k³ – k be divisible by 6.

So, we get,

⇒ k³ – k = 6x.

Now, we also get that,

⇒  P(k+1) = (k+1)³ – (k+1)

= (k+1)(k²+2k+1−1)

= k³ + 3k² + 2k

= 6x+3k(k+1) [n(n+1) is always even and divisible by 2]

= 6x + 3×(2y) Which is divisible by 6, where y = k(k+1)

⇒ P(k+1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = n³ – n is divisible by 6, for each natural number n.

According to the question,

P(n) = n(n² + 5) is divisible by 6.

So, substituting different values for n, we get,

P(0) = 0(0² + 5) = 0 Which is divisible by 6.

P(1) = 1(1² + 5) = 6 Which is divisible by 6.

P(2) = 2(2² + 5) = 18 Which is divisible by 6.

P(3) = 3(3² + 5) = 42 Which is divisible by 6.

Let P(k) = k(k² + 5) be divisible by 6.

So, we get,

⇒ k(k² + 5) = 6x.

Now, we also get that,

⇒  P(k+1) = (k+1)((k+1)² + 5) = (k+1)(k²+2k+6)

= k³ + 3k² + 8k + 6

= 6x+3k²+3k+6

= 6x+3k(k+1)+6[n(n+1) is always even and divisible by 2]

= 6x + 3×2y + 6 Which is divisible by 6.

⇒ P(k+1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = n(n² + 5) is divisible by 6, for each natural number n.

According to the question,

P(n) is n² < 2ⁿ  for n≥5

Let P(k) = k² < 2^k be true;

⇒ P(k+1) = (k+1)²

= k² + 2k + 1

2^k+1 = 2(2^k) > 2k²

Since, n² > 2n + 1 for n ≥3

We get that,

k² + 2k + 1 < 2k²

⇒ (k+1)² < 2^(k+1)

⇒ P(k+1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = n² < 2ⁿ is true for all natural numbers n ≥ 5.