Proof Mathematical Induction

Principle of mathematical induction

Consider a statement P(n), where n is a natural number. Then to determine the validity of P(n) for every n, use the following principle:

1. Check whether the given statement is true for n = 1.

2. Assume that given statement P(n) is also true for n = k, where k is any positive integer.

3. Prove that the result is true for P(k+1) for any positive integer k.

If the above-mentioned conditions are satisfied, then it can be concluded that P(n) is true for all n natural numbers.

Proof

The first step of the principle is a factual statement and the second step is a conditional one. According to this if the given statement is true for some positive integer k only then it can be concluded that the statement P(n) is valid for n = k + 1.

This is also known as the inductive step and the assumption that P(n) is true for n=k is known as the inductive hypothesis.

Solved problems

Example 1

Prove that the sum of cubes of n natural numbers is equal to $\left(\frac{n(n+1)}{2}\right)^2$ for all n natural numbers.

Solution:

In the given statement we are asked to prove:

$1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$

1. Step 1: Now with the help of the principle of induction in Maths, let us check the validity of the given statement P(n) for n=1.

$P(1) = \left(\frac{1(1+1)}{2}\right)^2 = \left(\frac{2}{2}\right)^2 = 1^2 = 1$

This is true.

2. Step 2: Now as the given statement is true for n=1, we shall move forward and try proving this for n=k, i.e.,

$1^3 + 2^3 + 3^3 + \cdots + k^3 = \left(\frac{k(k+1)}{2}\right)^2$

3. Step 3: Let us now try to establish that P(k+1) is also true.

$$\begin{aligned} 1^3 + 2^3 + 3^3 + \ldots + k^3 + (k+1)^3 &= \left[\frac{k(k+1)}{2}\right]^2 + (k+1)^3 \\ &= (k+1)^2 \left[ \frac{k^2}{4} + (k+1) \right] \\ &= (k+1)^2 \left( \frac{k^2 + 4k + 4}{4} \right) \\ &= (k+1)^2 \left( \frac{(k+2)^2}{4} \right) \\ &= \left[ \frac{(k+1)(k+2)}{2} \right]^2 \end{aligned}$$

Example 2

Show that $1 + 3 + 5 + \ldots + (2n-1) = n^2$

Solution:

1. Step 1: Result is true for n = 1

That is $1 = (1)^2$ (True)

2. Step 2: Assume that result is true for n = k

$1 + 3 + 5 + \ldots + (2k-1) = k^2$

3. Step 3: Check for n = k + 1

i.e. $1 + 3 + 5 + \ldots + (2(k+1)-1) = (k+1)^2$

We can write the above equation as,

$1 + 3 + 5 + \ldots + (2k-1) + (2(k+1)-1) = (k+1)^2$

Using step 2 result, we get

$k^2 + (2(k+1)-1) = (k+1)^2$

$k^2 + 2k + 2 - 1 = (k+1)^2$

$k^2 + 2k + 1 = (k+1)^2$

$(k+1)^2 = (k+1)^2$

L.H.S. and R.H.S. are same.

So the result is true for n = k+1

By mathematical induction, the statement is true.

We see that the given statement is also true for n=k+1. Hence we can say that by the principle of mathematical induction this statement is valid for all natural numbers n.

Example 3

Show that $2^{2n} - 1$ is divisible by 3 using the principles of mathematical induction.

To prove: $2^{2n} - 1$ is divisible by 3

Assume that the given statement be P(k)

Thus, the statement can be written as P(k) = $2^{2n} - 1$ is divisible by 3, for every natural number

1. Step 1: In step 1, assume n = 1, so that the given statement can be written as

$P(1) = 2^{2(1)} - 1 = 4 - 1 = 3$

So 3 is divisible by 3. (i.e. 3/3 = 1)

2. Step 2: Now, assume that P(n) is true for all the natural numbers, say k

Hence, the given statement can be written as

$P(k) = 2^{2k} - 1 \text{ is divisible by 3.}$

It means that $2^{2k} - 1 = 3a$ (where a belongs to natural number)

Now, we need to prove the statement is true for n = k+1

Hence,

$P(k+1) = 2^{2(k+1)} - 1$

$P(k+1) = 2^{2k+2} - 1$

$P(k+1) = 2^{2k} \cdot 2^2 - 1$

$P(k+1) = (2^{2k} \cdot 4) - 1$

$P(k+1) = 3 \cdot 2^{2k} + (2^{2k} - 1)$

The above expression can be written as

$P(k+1) = 3 \cdot 2^{2k} + 3a$

Now, take 3 outside, we get

$P(k+1) = 3(2^{2k} + a) = 3b, \text{ where "b" belongs to natural number}$

It is proved that p(k+1) holds true, whenever the statement P(k) is true.

Thus, $2^{2n} - 1$ is divisible by 3 is proved using the principles of mathematical induction