Mathematical Induction

Chapter 2

Mathematical Induction

2.1 Introduction
Mathematical induction is a powerful and elegant technique for proving certain type of mathematical statements, general propositions which assert that something is true for all natural numbers or for all natural numbers from some point on. One of the techniques to prove mathematical statements discussed in this chapter is the Principle of Mathematical Induction. The actual term mathematical induction was first used by De Morgan, even though the method was used by Fermat, Pascal and others before him. The method is used in many branches of higher mathematics.

Before we state the principle of mathematical induction, let us consider an example. Consider the sum of the first n odd positive integers. That is,

if n = 1,	1 = 1²,
if n = 2,	1 + 3	= 4	= 2² ,
if n = 3,	1 + 3 + 5	= 9	= 3² ,
if n = 4,	1 + 3 + 5 + 7	= 16	= 4²,
if n = 5,	1 + 3 + 5 + 7 + 9	= 25	= 5² ,
if n = 6,	1 + 3 + 5 + 7 + 9 + 11	= 36	= 6² ,

From the results above, it looks as if the sum of the first n odd natural numbers is always given by n². To express this statement symbolically, first observe that n^th odd natural number is 2n - 1. Then the statement can be expressed as:

1 + 3 + 5 + 7 + 9 + ... + (2n - 1) = n² (1)

Although from this pattern we might conjecture that statement (1) is true for any choice of n, can we really be sure that it does not fail for some choice of n ? We have seen that the statement is true for n = 1, 2, 3, 4, 5, 6 by direct calculation. Is the statement true for any natural number n? Actually, no matter how many cases we check, we can never prove that the statement is always true because there are infinitely many cases and direct calculation cannot check them all. The method of prove by mathematical induction will, in fact, prove that any mathematical statement like (1) is true for all natural numbers n.

2.2 Principle of Mathematical Induction

For each natural number n, let P(n) be a statement depending on n. Suppose that the following two conditions are satisfied.

1. The statement is true for n = 1.

2. For any natural number k, if the statement is true for n = k, then the statement is true for n = k + 1.

Then the statement P(n) is true for all natural number n.

To apply this principle, there are two steps:

The initial step: Prove that the statement is true for n = 1.

The inductive step: Assume that the statement is true for n = k, and use this assumption to prove that the statement is true for n = k + 1.

Conclusion: The statement have been proved for n = 1. By the inductive step, since the statement is true for n = 2, it is also true for n = 3. And since the statement is true for n = 3, it is also true for n = 4, and so on. Finally, we conclude that the statement is true for all natural numbers n.

Example 1.

Use the mathematical induction principle to prove that 1 + 3 + 5 + ... + (2n - 1) = n² , for all natural numbers n.

Solution
Let P(n) denote the statement 1 + 3 + 5 + ... + (2n - 1) = n².
(1) For n = 1, L.H.S = 1,
R.H.S = 1² = 1
L.H.S = R.H.S
The statement is true for n = 1.

(2) Assume that the statement is true for n = k, that is

1 + 3 + 5 + ... + (2k - 1) = k²

We will show that the statement is true for n = k + 1,that is we have to show that

1 + 3 + 5 + ... + (2k - 1) + [2(k + 1) - 1] = (k + 1)²

It is proved that

1 + 3 + 5 + ... + (2k - 1) + [ 2(k + 1) - 1]	= k² + [2(k + 1) - 1]
	= k² + 2k + 2 - 1
	= k² + 2k + 1
	= (k + 1)²

Therefore, the statement is true for n = k + 1.

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

Example 2.
Use the mathematical induction principle to prove that 1 + 2 + 3 + ... + n = ^{n(n + 1)} ⁄ ₂, for all natural numbers n.

Solution
Let P(n) denote the statement 1 + 2 + 3 + ... + n = ^{n(n + 1)} ⁄ ₂,
(1) For n = 1, L.H.S = 1
R.H.S = ^{1(1 + 1)} ⁄ ₂ = 1.
L.H.S = R.H.S
The statement is true for n = 1.

(2) Assume that the statement is true for n = k, that is
1 + 2 + 3 + ... + k = ^{k(k + 1)} ⁄ ₂
We will show that the statement is true for n = k + 1, that is we have to show that
1 + 2 + 3 + ... + k + (k + 1) = ^{(k + 1)(k + 2)} ⁄ ₂
It is proved that

1 + 2 + 3 + ... + k + (k + 1)	= ^{k(k + 1)} ⁄ ₂ + (k + 1)
	= ^{k² + k + 2k + 2} ⁄₂
	= ^{k² + 3k + 2} ⁄ ₂
	= ^{(k + 1)(k + 2)} ⁄ ₂

Therefore, the statement is true for n = k + 1.

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

In some cases, a statement involving a variable n holds when the natural numbers n ≥ m, m ∈ N and the stastement does not hold when n < m. In this case, we will prove that the statement is true for n = m in the initial step.

Example 3.
Use the mathematical induction principle to prove that 3ⁿ - 1 is a multiple of 2.

Solution
Let P(n) denotes the statement 3ⁿ - 1 is a multiple of 2.
(1) For n = 1, 3¹ - 1 = 2 which is a multiple of 2.
The statement is true for n = 1.

(2) Assume that the statement is true for n = k, that is
3^k - 1 is a multiple of 2.
We will show that the statement is true for n = k + 1, that is we have to show that 3^k+1 - 1 is a multiple of 2.
we prove that 3^k+1 - 1 = 3 . 3^k - 1 = 2 . 3^k + 3^k - 1.
Since 2 . 3^k is a multiple of 2 and 3^k - 1 is a multiple of 2, we can say that 2 . 3^k + 3^k - 1 is also a multiple of 2.
So, 3^k+1 - 1 is also a multiple of 2.
Therefore, the statement is true for n = k + 1.

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

Example 4.
Prove that (ab)ⁿ = aⁿbⁿ for every natural number n.

Solution
Let P(n) denote the statement (ab)ⁿ = aⁿbⁿ.

(1) For n = 1, L.H.S = (ab)¹ = ab
R.H.S = a¹b¹ = ab.
L.H.S = R.H.S

The statement is true for n = 1.

(2) Assume that the statement is true for n = k, that is.
(ab)^k = a^kb^k
We will show that the statement is true for n = k + 1, that is we have to show that
(ab)^k+1 = a^k+1b^k+1.
it is proved that
(ab)^k+1 = (ab)^k(ab) = (a^kb^k (ab) = (a^ka)(b^kb) = a^k+1b^k+1
Therefore, the statement is true for n = k + 1.

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

Example 5.
Prove that 1 ⋅ 3 + 2 ⋅ 3² + 3 ⋅ 3³ + ... + n ⋅ 3ⁿ = ^{(2n - 1)3ⁿ⁺¹ + 3} ⁄ ₄ for all natural numbers n by the use of the mathematical induction principle.

Solution

Let P(n) denote the statement 1 ⋅ 3 + 2 ⋅ 3² + 3 ⋅ 3³ + ... + n ⋅ 3ⁿ = ^{(2n - 1)3ⁿ⁺¹ + 3} ⁄ ₄.

(1) For n = 1,	L.H.S = 1 ⋅ 3 = 3,
	R.H.S = ^{(2 - 1)3² + 3} ⁄ ₄ = ¹² ⁄ ₄ = 3.
	L.H.S = R.H.S

The statement is true for n = 1.

(2) Assume that the statement is true for n = k, that is
1 ⋅ 3 + 2 ⋅ 3² + 3 ⋅ 3³ + ... + k ⋅ 3^k = ^{(2k - 1)3^k+1 + 3} ⁄ ₄

We will show that the statement is true for n = k + 1, that is we have to show that

1 ⋅ 3 + 2 ⋅ 3² + 3 ⋅ 3³ + ... + k ⋅ 3^k + (k + 1) ⋅ 3^k+1 = ^{(2(k + 1) - 1) 3^k+2 + 3} ⁄ ₄

It is proved that

1⋅3 + 2⋅3² + 3⋅3³ +...+ k⋅3^k + (k + 1)⋅3^k+1	= ^{(2k - 1)3^k+1 + 3} ⁄ ₄ + (k + 1)3^k+1
	= ^{(2k - 1)3^k+1 + 3 + 4(k + 1)3^k+1} ⁄ ₄
	= ^{(6k + 3)3^k+1 + 3} ⁄ ₄
	= ^{(2k + 1)3^k+2 + 3} ⁄ ₄
	= ^{(2(k + 1) - 1)3^k+2 + 3} ⁄ ₄

Therefore, the statement is true for n = k + 1.

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

Example 6.
Use the mathematical induction principle to prove that a - b is a factor of aⁿ - bⁿ for all natural numbers n.

Solution

Let P(n) denote the statement a - b is a factor of aⁿ - bⁿ.

(1) For n = 1, a¹ - b¹ = a - b.

So, a - b is a factor of a¹ - b¹.

The statement is true for n = 1.

(2) Assume that the statement is true for n = k, that is a - b is a factor of a^k - b^k.

We will show that the statement is true for n = k + 1, that is we have to show that a - b is a factor of a^k+1 - b^k+1.

It is proved that

a^k+1 - b^k+1	= a^k+1 - a^kb + a^kb - b^k+1
	= a^k(a - b) + b(a^k - b^k).

Since a - b is a factor of a^k(a - b) and a - b is a factor of a^k - b^k, a - b is also a factor of a^k(a - b) + b(a^k - b^k). So, a - b is a factor of a^k+1 - b^k+1.

Therefore, the statement is true for n = k + 1.

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

Example 7.
Use the mathematical induction principle to prove that 4n < 2ⁿ for all natural numbers n ≥ 5.

Solution

Let P(n) denote the statement 4n < 2ⁿ.

(1) For n = 5,	L.H.S	= 4(5) = 20
	R.H.S	= 2⁵ = 32
	L.H.S	< R.H.S

The statement is true for n = 5.

(2) Assume that the statement is true for n = k ≥ 5, that is

4k < 2^k

We will show that the statement is true for n = k + 1, that is we have to show that 4(k + 1) < 2^k+1.

It is proved that

4(k + 1)	= 4k + 4
	< 2^k + 4
	< 2^k + 4k (since 4 < 4k)
	< 2^k + 2^k
	= 2 . 2^k = 2^k+1

Hence, 4(k + 1) < 2^k+1.

Therefore, the statement is true for n = k + 1.

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

Ecercise 2.1

Prove the following by using the principle of mathematical induction for all natural numbers n:

^n-1

^{3ⁿ - 1} ⁄ ₂

^{n(n + 1)} ⁄ ₂

^{n(n + 1)(n + 2)} ⁄ ₃

¹ ⁄ ₂

¹ ⁄ ₄

¹ ⁄ ₈

¹ ⁄ _2ⁿ

^n-1

ⁿ

¹ ⁄ _{1 . 2}

¹ ⁄ _{2 . 3}

¹ ⁄ _{3 . 4}

¹ ⁄ _{n(n + 1)}

ⁿ ⁄ _{n + 1}

Prove that 3 is a factor of 4ⁿ - 1 for all natural numbers n by using the mathematical induction.

Prove that n³ - n + 3 is divisible by 3 for all natural numbers n by using the mathematical induction.

Prove that 3²ⁿ - 1 is divisible by 8 for all natural numbers n by using the mathematical induction.

Prove that (n + 1)² < 2n² for all natural numbers n ≥ 3 by using the mathematical induction.

Prove that (2n + 7) < (n + 3)² for all natural numbers n by using the mathematical induction.

Prove that x²ⁿ - y²ⁿ is divisible by x + y for all natural numbers n using the mathematical induction.