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 = 12,
if n = 2, 1 + 3 = 4 = 22 ,
if n = 3, 1 + 3 + 5 = 9 = 32 ,
if n = 4, 1 + 3 + 5 + 7 = 16 = 42,
if n = 5, 1 + 3 + 5 + 7 + 9 = 25 = 52 ,
if n = 6, 1 + 3 + 5 + 7 + 9 + 11     = 36    = 62 ,

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

1 + 3 + 5 + 7 + 9 + ... + (2n - 1) = n2             (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) = n2 , for all natural numbers n.

Solution
Let P(n) denote the statement 1 + 3 + 5 + ... + (2n - 1) = n2.
(1)    For n = 1, L.H.S = 1,
R.H.S = 12 = 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) = k2

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)2

It is proved that

1 + 3 + 5 + ... + (2k - 1) + [ 2(k + 1) - 1] = k2 + [2(k + 1) - 1]
= k2 + 2k + 2 - 1
= k2 + 2k + 1
= (k + 1)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 2.
Use the mathematical induction principle to prove that 1 + 2 + 3 + ... + n = n(n + 1) 2, for all natural numbers n.

Solution
Let P(n) denote the statement 1 + 2 + 3 + ... + n = n(n + 1) 2,
(1) For n = 1, L.H.S = 1
R.H.S = 1(1 + 1) 2 = 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) 2
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) 2
It is proved that
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1) 2 + (k + 1)
= k2 + k + 2k + 2 2
= k2 + 3k + 2 2
= (k + 1)(k + 2) 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 nm, mN 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 3n - 1 is a multiple of 2.

Solution
Let P(n) denotes the statement 3n - 1 is a multiple of 2.
(1) For n = 1,     31 - 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
3k - 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 3k+1 - 1 is a multiple of 2.
we prove that 3k+1 - 1 = 3 . 3k - 1 = 2 . 3k + 3k - 1.
Since 2 . 3k is a multiple of 2 and 3k - 1 is a multiple of 2, we can say that 2 . 3k + 3k - 1 is also a multiple of 2.
So, 3k+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)n = anbn for every natural number n.

Solution
Let P(n) denote the statement (ab)n = anbn.

(1) For n = 1, L.H.S = (ab)1 = ab
R.H.S = a1b1 = 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 = akbk
We will show that the statement is true for n = k + 1, that is we have to show that
(ab)k+1 = ak+1bk+1.
it is proved that
(ab)k+1 = (ab)k(ab) = (akbk (ab) = (aka)(bkb) = ak+1bk+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 . 32 + 3 . 33 + ... + n . 3n = (2n - 1)3n+1 + 3 4 for all natural number n by the use of the mathematical induction principle.

Solution

Let P(n) denote the statement 1 . 3 + 2 . 32 + 3 . 33 + ... + n . 3n = (2n - 1)3n+1 + 3 4.
(1) For n = 1, L.H.S = 1 . 3 = 3,
R.H.S = (2 - 1)32 + 3 4 = 12 4 = 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 . 32 + 3 . 33 + ... + k . 3k = (2k - 1)3k+1 + 3 4

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

1 . 3 + 2 . 32 + 3 . 33 + ... + k . 3k + (k + 1) . 3k+1 = (2(k + 1) - 1) 3k+2 + 3 4

It is prove that

1 . 3 + 2 . 32 + 3 . 33 + ... + k . 3k + (k + 1) . 3k+1 = (2k - 1)3k+1 + 3 4 + (k + 1)3k+1
= (2k - 1)3k+1 + 3 + 4(k + 1)3k+1 4
= (6k + 3)3k+1 + 3 4
= (2k + 1)3k+2 + 3 4
= (2(k + 1) - 1)3k+2 + 3 4

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 an - bn for all natural numbers n.

Solution

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

(1) For n = 1, a1 - b1 = a - b.

So, a - b is a factor of a1 - b1.

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 ak - bk.

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 ak+1 - bk+1.

It is proved that

ak+1 - bk+1 = ak+1 - akb + akb - bk+1
= ak(a - b) + b(ak - bk).

Since a - b is a factor of ak(a - b) and a - b is a factor of ak - bk, a - b is also a factor of ak(a - b) + b(ak - bk). So, a - b is a factor of ak+1 - bk+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 < 2n for all natural numbers n ≥ 5.

Solution

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

(1) For n = 5, L.H.S = 4(5) = 20
R.H.S = 25 = 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 < 2k

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

It is proved that
4(k + 1) = 4k + 4
< 2k + 4
< 2k + 4k   (since 4 < 4k)
< 2k + 2k
= 2 . 2k = 2k+1

Hence, 4(k + 1) < 2k+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
  1. Prove the following by using the principle of mathematical induction for all natural numbers n:
  2. (a) 1 + 3 + 32 + ... + 3b = 3n - 1 2

    (b) 13 + 23 + 33 + ... + n3 = (n(n + 1) 2)2

    (c) 23 + 43 + 63 + ... + (2n)3 = 2n2(n + 1)2

    (d) 1⋅2 + 2⋅3 + 3⋅4 + ... + n(n + 1) = n(n + 1)(n + 2) 3

    (e) 1 2 + 1 4 + 1 8 + ... + 1 2n = 1 - 1 2n

    (f) 1 + 2 + 22 + ... + 2n-1 = 2n - 1

    (g) 1 1 . 2 + 1 2 . 3 + 1 3 . 4 + ... + 1 n(n + 1) = n n + 1

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

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

  5. Prove that 32n - 1 is divisible by 8 for all natural numbers n by using the mathematical induction.

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

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

  8. Prove that x2n - y2n is divisible by x + y for all natural numbers n using the mathematical induction.


Answers

  1. Prove the following by using the principle of mathematical induction for all natural numbers n:
  2. (a) 1 + 3 + 32 + ... + 3n - 1 = 3n - 1 2

    Solution

    Let P(n) denote the statement 1 + 3 + 32 + ... + 3n-1 = 3n - 1 2
    (1) For n = 1,     L.H.S = 1
    R.H.S = 31 - 1 2 = 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 + 32 + ... + 3k+1 = 3k - 1 2
    We will show that the statement is true for n = k + 1, that is we have to show that

    1 + 3 + 32 + ... + 3k-1 + [3k+1 - 1] = 3k+1 - 1 2
    It is proved that

    1 + 3 + 32 + ... + 3k-1 + [3k] = 3k - 1 2 + [3k]
    = 3k - 1 2 + 2 ⋅ 3k2
    = 3k - 1 + 2 ⋅ 3k 2
    = 3k + 2 ⋅ 3k - 1 2
    = 3k(1 + 2) - 1 2
    = 3k . 3 - 1 2
    = 3k+1 - 1 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.

    (b) 13 + 23 + 33 + ... + n3 = (n(n + 1) 2)2

    Solution
    Let P(n) denote the statement 13 + 23 + 33 + ... + n3 = (n(n + 1) 2)2

    For n = 1,
    L.H.S = 13
    = 1
    R.H.S = ( 1 (1 + 1)2 )2
    = ( 22 )2
    = 12
    = 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
    13 + 23 + 33 + ... + k3 = (k (k + 1) 2)2

    We will show that the statement is true for n = k + 1, that is we have to show that
    13 + 23 + 33 + ... + k3 + [(k + 1)3] = [(k + 1) {(k + 1) + 1 } 2]2
    = [(k + 1) (k + 2) 2]2

    It is proved that
    13 + 23 + 33 + ... + k3 + [(k + 1)3] = [k (k + 1) 2]2 + (k + 1)3
    = k 2 (k + 1)2 4 + 4 (k + 1)34
    = k 2 (k + 1)2   +   4 (k + 1) 3 4
    = k 2 (k + 1)2   +   4 (k + 1) (k + 1) 2 4
    = (k + 1)2 ( k2   +   4 (k + 1)) 4
    = (k + 1)2 ( k2 + 4k + 4) 4
    = (k + 1)2 (k + 2)2 4
    = [(k + 1) (k + 2) 2]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.

    (c) 23 + 43 + 63 + ... + (2n)3 = 2n2(n + 1)2

    Solution
    Let P(n) denote the statement 23 + 43 + 63 + ... + (2n)3 = 2n2(n + 1)2
    (1) Fon n = 1,
    L.H.S = 23
    = 8
    R.H.S = 2 ⋅ 12 (1 + 1)2
    = 2 (2)2
    = 8
    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
    23 + 43 + 63 + ... + (2k)3 = 2k2(k + 1)2
    We will show that the statement is true for n = k + 1, that is
    we have to show that
    23 + 43 + 63 + ... + (2k)3 + [2 (k+1)]3 = 2(k+1)2(k+1 + 1)2
    23 + 43 + 63 + ... + (2k)3 + [8 (k+1)3] = 2(k+1)2(k + 2)2
    It is proved that
    23 + 43 + 63 + ... + (2k)3 + [8 (k+1)3] = 2k2 (k + 1)2 + [8 (k + 1)3]
    = 2k2 (k + 1)2 + 8 (k + 1) (k + 1)2
    = (k + 1)2 (2k2   +   8 (k + 1) )
    = (k + 1)2 (2k2 + 8k + 8 )
    = (k + 1)2  2 (k2 + 4k + 4 )
    = (k + 1)2   2 (k + 2)2
    = 2 (k + 1)2 (k + 2)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.

    (d) 1⋅2 + 2⋅3 + 3⋅4 + ... + n(n + 1) = n (n + 1)(n + 2) 3

    Solution
    Let P(n) denote the statement 1⋅2 + 2⋅3 + 3⋅4 + ... + n(n + 1) = n (n + 1)(n + 2) 3

    (1) For n = 1,
    L.H.S = 1 ⋅ 2
    = 2
    R.H.S = 1 (1 + 1) (1 + 2)3
    = 2 (3)3
    = 2
    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 + 2⋅3 + 3⋅4 + ... + k(k + 1) = k (k + 1)(k + 2) 3

    We will show that the statement is true for n = k + 1, that is
    we have to show that
    1⋅2 + 2⋅3 + 3⋅4 + ... + k(k + 1) + [(k+1) (k+1 + 1)] = (k+1) (k+1 + 1)(k+1 + 2) 3

    1⋅2 + 2⋅3 + 3⋅4 + ... + k(k + 1) + [(k+1) (k + 2)] = (k+1) (k + 2)(k + 3) 3

    It is preved that
    1⋅2 + 2⋅3 + 3⋅4 + ... + k(k + 1) + [(k+1) (k + 2)] = (k+1) (k + 2) 3 + (k + 1) (k + 2)
        = k (k + 1) (k + 2)3 + 3 (k + 1) (k + 2)3
        = k (k + 1) (k + 2)   +   3 (k + 1) (k + 2)3
        = k (k + 1) (k + 2)   +   3 (k + 1) (k + 2)3
        = (k + 1) (k + 2) (k   +   3) 3
        = (k + 1) (k + 2) (k + 3) 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.

    (e) 1 2 + 1 4 + 1 8 + ... + 1 2n = 1 - 1 2n

    Solution
    Let P(n) denote the statement
    1 2 + 1 4 + 1 8 + ... + 1 2n = 1 - 1 2n

    (1) For n = 1,
    L.H.S = 12
    R.H.S = 1 - 121
    = 1 ⋅ 22 - 12
    = 2 - 12
    = 12
    L.H.S = R.H.S

    The statement is true for n = 1.

    Assume that the statement is true for n = k, that is
    1 2 + 1 4 + 1 8 + ... + 1 2k = 1 - 1 2k

    We will show that the statement is true for n = k + 1, that is
    we have to show that
    1 2 + 1 4 + 1 8 + ... + 1 2k + [ 12k + 1 ] = 1 - 1 2k + 1
    It is proved that
    1 2 + 1 4 + 1 8 + ... + 1 2k + [ 12k + 1 ] = 1 - 1 2k + 12k + 1

        = 1 + [ - 12k + 12k + 1 ]
        = 1 + [ - 1 ⋅ 2 2k ⋅ 2 + 1 2k + 1 ]
        = 1 + [ - 22k + 1 + 12k + 1 ]
        = 1 + [ - 2 + 12 k + 1 ]
        = 1 - 12 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.

    (f) 1 + 2 + 22 + ... + 2n-1 = 2n - 1

    Solution
    Let P(n) denote the statement 1 + 2 + 22 + ... + 2n-1 = 2n - 1

    For n = 1,
    L.H.S = 1
    R.H.S = 21 - 1
    = 2 - 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 + 22 + ... + 2k-1 = 2k - 1

    We will show that the statement is true for n = k + 1, that is
    we have to show that
    1 + 2 + 22 + ... + 2k-1 + [2k+1 - 1] = 2k+1 - 1

    1 + 2 + 22 + ... + 2k-1 + [2k] = 2k + 1 - 1

    It is proved that
    1 + 2 + 22 + ... + 2k-1 + [2k] = 2k - 1 + 2k
    = 2k + 2k - 1
    = 2 ⋅ 2k - 1
    = 2k ⋅ 21 - 1
    = 2k + 1 - 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.

    (g) 1 1 . 2 + 1 2 . 3 + 1 3 . 4 + ... + 1 n(n + 1) = n n + 1

    Solution
    Let P(n) denote the statement 1 1 . 2 + 1 2 . 3 + 1 3 . 4 + ... + 1 n(n + 1) = n n + 1

    (1) For n = 1,
    L.H.S = 11 ⋅ 2
    = 12
    R.H.S = 11 + 1
    = 12
    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 1 . 2 + 1 2 . 3 + 1 3 . 4 + ... + 1 k(k + 1) = k k + 1

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

    1 1 . 2 + 1 2 . 3 + 1 3 . 4 + ... + 1 n(n + 1) + [ 1(k+1) (k + 2) ] = k+1 k + 2

    It is proved that
    1 1 . 2 + 1 2 . 3 + 1 3 . 4 + ... + 1 n(n + 1) + [ 1(k+1) (k + 2) ] = k k + 1 + 1(k + 1) (k + 2)
        = k (k + 2) (k + 1) (k + 2) + 1(k + 1) (k + 2)
        = k (k + 2) + 1 (k + 1) (k + 2)
        = k2 + 2k + 1 (k + 1) (k + 2)
        = (k + 1) (k + 1) (k + 1) (k + 2)
        = k + 1 k + 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.

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

  4. Solution
    Let P(n) denote the statement 3 is a factor of 4n - 1.
    (1) For n = 1,
    41 - 1 = 4 - 1
    = 3
    3 is a factor of 41 - 1
    The statement is true for n = 1.

    (2) Assume that the statement is true for n = k + 1, that is we have to show that 3 is a factor of 4k + 1 - 1.
    It is proved that
    4k + 1 - 1 = 4k ⋅ 41 - 1
    = 4 ⋅ 4k - 1
    = 3 ⋅ 4k + 1 ⋅ 4k   - 1
    = 3 ⋅ 4k + 4k - 1

    Since 3 is a factor of 3 ⋅ 4k and 4k - 1, we can say that 3 is also a factor of 3 ⋅ 4k + 4k - 1.
    So 3 is also a factor of 4k + 1 - 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. Prove that n3 - n + 3 is divisible by 3 for all natural numbers n by using the mathematical induction.

  6. Solution
    Let P(n) denote the statement n3 - n + 3 is divisible by 3.
    (1) For n = 1,
    13 - 1 + 3 = 3 which is divisible by 3.
    The statement is true for n = 1.

    (2) Assume that the statement is true for n = k, that is k3 - k + 3 is divisible by 3.
    We will show that the statement is true for n = k + 1, that is
    we have to show that
    (k + 1)3 - (k + 1) + 3 = k3 + 3k2 + 3k + 1 - k - 1 + 3
    = k3 - k + 1 - 1 + 3 + 3k2 + 3k
    = k3 - k + 3 + 3(k2 + k)

    Since k3 - k + 3 is divisible by 3 and 3 (k2 + k) is also divisible by 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.

  7. Prove that 32n - 1 is divisible by 8 for all natural numbers n by using the mathematical induction.

  8. Solution
    Let P(n) denote the statement 32n - 1 is divisible by 8.
    (1) For n = 1,
    32n - 1 = 32 - 1
    = 9 - 1
    = 8
    which is divisible by 8.
    The statement is true for n = 1.

    (2) Assume that the statement is true for n = k, that is 32k - 1 is divisible by 8.
    We will show that the statement is true for n = k + 1, that is
    we have to show that
    32k + 1 is divisible by 8.
    It is proved that
    32(k+1) - 1 = 32k + 2 - 1
    = 32k ⋅ 32 - 1
    = 32k ⋅ 9 - 1
    = 9 ⋅ 32k - 1
    = 8 ⋅ 32k + 1 ⋅ 32k - 1
    = 8 ⋅ 32k + 32k - 1
    Since 8 ⋅ 32k is divisible by 8 and 32k - 1 is divisible by 8, So, 32(k+1) - 1 is also divisible by 8.
    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.

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

  10. Solution
    Let P(n) denote the statement (n + 1)2 < 2n2
    (1) For n = 3,
    L.H.S = (3 + 1)2
    = 42
    = 16
    R.H.S = 2 (3)2
    = 2 (9)
    = 18
    L.H.S < R..H.S

    The statement is true for n = 3.

    (2) Assume that the statement is true for n = k ≥ 3, that is (k + 1)2 < 2k2.
    We will show that the statement is true for n = k + 1, that is
    we have to show that
    (k+1 + 1)2 < 2 (k+1)2
    (k + 2)2 < 2 (k + 1)2
    It is proved that
    (k + 1)2 < 2k2
    Add 4k + 2 at both sides
    (k + 1)2 + 4k + 2 < 2k2 + 4k + 2
    k2 + 2k + 1   + 4k + 2 < 2 (k2 + 2k + 1)
    k2 + 6k + 3 < 2 (k + 1)2
    k2 + 4k + 4 < 2 (k + 1)2     (∵ for k ≥ 3, k2 + 4k + 4   <   k2 + 6k + 3)
    ∴ (k + 2)2 < 2 (k + 1)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 ≥ 3.

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

  12. Solution
    Let P(n) denote the statement (2n + 7) < (n + 3)2
    (1) For n = 1,
    L.H.S = 2 (1) + 7
    = 9
    R.H.S = (1 + 3)2
    = 42
    = 16
    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 (2k + 7) < (k + 3)2
    We will show that the statement is true for n = k + 1, that is
    we have to show that
    ( 2 (k+1) + 7 ) < (k+1 + 3)2
    (2k + 2 + 7) < (k + 4)2
    (2k + 9) < (k + 4)2

    It is proved that
    (2k + 7) < (k + 3)2
    (2k + 7) < (k2 + 6k + 9)
    Add 2 both sides
    (2k + 7 + 2) < (k2 + 6k + 9 + 2)
    (2k + 9) < (k2 + 6k + 11)
    (2k + 9) < (k2 + 8k + 16)     (∵ (k2 + 6k + 11) < ( k2 + 8k + 16) )
    ∴ (2k + 9) < (k + 4)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.

  13. Prove that x2n - y2n is divisible by x + y for all natural numbers n using the mathematical induction.
    Solution
    Let P(n) denote the statement x2n - y2n is divisible by x + y.
    (1) For n = 1,
    x2 (1) - y2 (1) = x2 - y2
    = (x + y) (x - y)
    which is divisible by x + y.
    The statement is true for n = 1.

    (2) Assume that the statement is true for n = k, that is x2k - y2k is divisible by x + y.
    We will show that the statement is true for n = k + 1, that is
    we have to show that
    x2(k+1) - y2 (k+1) is divisible by x + y.
    It is proved that
    x2 (k +1)   -   y2 (k + 1) = x2k + 2   -   y2k + 2
    = x2kx2   -   y2ky 2
    = x2x2k   -  y2ky 2
    = x2 (x2k - y2k + y 2k)   -   y2ky2
    = x2 (x2k - y2k) + x2y2k   -   y2ky2
    = x2 (x2k - y2k)   +   y2k (x2 - y2)
    Since x2 - y2 is divisible by x + y and x2k - y2k is divisible by x + y, we can say that x2 (x2k - y2k)   +   y2k (x2 - y2) is also divisible by x + y.
    So, x2 (k +1)   -   y2 (k + 1) is also divisible by x + y.

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


image