2.0 Principle of mathematical induction

Suppose there is a given statement $P(n)$ involving the natural number $n$ such that

(i) The statement is true for $n = 1$, i.e., $P(1)$ is true, and

(ii) If the statement is true for $n = k$ (where $k$ is some positive integer), then the statement is also true for $n = k + 1$, i.e., truth of $P(k)$ implies the truth of $P (k + 1)$.

Then, $P(n)$ is true for all natural numbers $n$.

Property 1: It is simply a statement of fact. There may be situations when a statement is true for all $n ? 4$. In this case, step $1$ will start from $n = 4$ and we shall verify the result for $n = 4$, i.e., $P(4)$.

Property 2: It is a conditional property. It does not assert that the given statement is true for $n = k$, but only that if it is true for $n = k$, then it is also true for $n = k +1$. So, to prove that the property holds, only prove that conditional proposition:

If the statement is true for $n = k$, then it is also true for $n = k + 1$. This is sometimes referred to as the inductive step. The assumption that the given statement is true for $n = k$ in this inductive step is called the inductive hypothesis.

Question 1. For all $n ? 1$, prove that

$${1^2} + {2^2} + {3^2} + {4^2} + {5^2} + ..... + {n^2} = \frac{{n(n + 1)(2n + 1)}}{6}$$

Solution: Let the given statement be $P(n)$, i.e.,

$$\begin{equation} \begin{aligned} P(n) = {1^2} + {2^2} + {3^2} + {4^2} + {5^2} + ..... + {n^2} = \frac{{n(n + 1)(2n + 1)}}{6} \\ n = 1,P(1):1 = \frac{{1.(1 + 1)(2 + 1)}}{6} = \frac{{2 \times 3}}{6} = 1 \\ \\\end{aligned} \end{equation} $$ which is true.

Assume that $P(k)$ is true for some positive integers $k$, i.e.,

$${1^2} + {2^2} + {3^2} + {4^2} + {5^2} + ..... + {k^2} = \frac{{k(k + 1)(2k + 1)}}{6}...(i)$$

We will now prove that $P(k + 1)$ is also true. Now, we have

$$\begin{equation} \begin{aligned} ({1^2} + {2^2} + {3^2} + {4^2} + {5^2} + ..... + {k^2}) + {(k + 1)^2} \\ = \frac{{k(k + 1)(2k + 1)}}{6} + {(k + 1)^2} \\ = \frac{{k(k + 1)(2k + 1) + 6{{(k + 1)}^2}}}{6} \\ = \frac{{(k + 1)(2{k^2} + 7k + 6)}}{6} \\ = \frac{{(k + 1)(k + 1 + 1)\{ 2(k + 1) + 1\} }}{6} \\\end{aligned} \end{equation} $$

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

Hence, from the principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $N$.

Question 2. Prove that $2n > n$ for all positive integers $n$.

Solution: Let $$P(n):{2^n} > n$$

for $n=1$, $${2^1} > 1$$ Hence P(1) is true.

Assume that $P(k)$ is true for any positive integers $k$, i.e., $2k > k ... (1)$

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

Multiplying both sides of $(1)$ by $2$, we get

$$2. 2k > 2k$$

$${2^{k + 1}} > 2k > k + k > k + 1$$

Therefore, $P(k + 1)$ is true when $P(k)$ is true. Hence, by principle of mathematical induction, $P(n)$ is true for every positive integer $n$.

Question 3. Prove the following by using the principle of mathematical induction for all $n ? N$

$$1 + {3^1} + {3^2} + {3^3} + ... + {3^{n-1}} = \frac{{{3^n} - 1}}{2}$$

Solution: Let the given statement be P(n), i.e.,

$$P(n):1 + {3^1} + {3^2} + {3^2} + ... + {3^{n - 1}} = \frac{{{3^n} - 1}}{2}$$

For $n = 1$, we have

$$P(1):1 = \frac{{{3^1} - 1}}{2} = \frac{2}{2} = 1$$ which is true

Let $P(k)$ be true for some positive integer $k$, i.e.,

$$1 + {3^1} + {3^2} + {3^2} + ... + {3^{k - 1}} = \frac{{{3^k} - 1}}{2}...(i)$$

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

Consider $$\begin{equation} \begin{aligned} 1 + {3^1} + {3^2} + {3^2} + ... + {3^{k - 1}} + {3^{(k + 1) - 1}} \\ (1 + {3^1} + {3^2} + {3^2} + ... + {3^{k - 1}}) + {3^k} \\ = \frac{{({3^k} - 1)}}{2} + {3^k} \\ = \frac{{({3^k} - 1) + {{2.3}^k}}}{2} \\ = \frac{{(1 + 2){3^k} - 1}}{2}n = 1,{2^1} > 1 \\ = \frac{{{{3.3}^k} - 1}}{2} \\ = \frac{{{3^{k + 1}} - 1}}{2} \\\end{aligned} \end{equation} $$

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

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

Question 4. Prove the following by using the principle of mathematical induction for all $n ? N$.

$${1^3} + {2^3} + {3^3} + {4^3} + ...{n^3} = {\{ \frac{{n(n + 1)}}{2}\} ^2}$$

Solution: Let the given statement be $P(n)$, i.e.,

$${1^3} + {2^3} + {3^3} + {4^3} + ...{n^3} = {\{ \frac{{n(n + 1)}}{2}\} ^2}$$

$P(n)$: For $n = 1$, we have

$$P(1):{1^3} = 1 = {\{ \frac{{1(1 + 1)}}{2}\} ^2} = {(\frac{{1.2}}{2})^2} = 1$$ which is true

Let $P(k)$ be true for some positive integer $k$, i.e.,

$${1^3} + {2^3} + {3^3} + {4^3} + ...{k^3} = {\{ \frac{{k(k + 1)}}{2}\} ^2}...(i)$$

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

Consider

$$\begin{equation} \begin{aligned} {1^3} + {2^3} + {3^3} + {4^3} + ...{k^3} + {(k + 1)^3} \\ = {\{ \frac{{k(k + 1)}}{2}\} ^2} + {(k + 1)^3} \\ = \frac{{{k^2}{{(k + 1)}^2}}}{4} + {(k + 1)^3} \\ = \frac{{{k^2}{{(k + 1)}^2} + 4{{(k + 1)}^3}}}{4} \\ = \frac{{{{(k + 1)}^2}({k^2} + 4(k + 1))}}{4} \\ = \frac{{{{(k + 1)}^2}({k^2} + 4k + 4)}}{4} \\ = \frac{{{{(k + 1)}^2}{{(k + 2)}^2}}}{4} \\ = \frac{{{{(k + 1)}^2}{{(k + 1 + 1)}^2}}}{4} \\ = {\{ \frac{{(k + 1)(k + 1 + 1)}}{2}\} ^2} \\ = {1^3} + {2^3} + {3^3} + {4^3} + ...{k^3} + {(k + 1)^3} \\\end{aligned} \end{equation} $$

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

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

Question 5. Prove the following by using the principle of mathematical induction for all $n ? N$:

$$1 + \frac{1}{{(1 + 2)}} + \frac{1}{{(1 + 2 + 3)}} + ... + \frac{1}{{(1 + 2 + 3 + ... + n)}} = \frac{{2n}}{{n + 1}}$$

Solution: Let the given statement be $P(n)$, i.e.,

$$P(n):1 + \frac{1}{{(1 + 2)}} + \frac{1}{{(1 + 2 + 3)}} + ... + \frac{1}{{(1 + 2 + 3 + ... + n)}} = \frac{{2n}}{{n + 1}}$$

For $n = 1$, we have

$$P(1):1 = \frac{{2.1}}{{1 + 1}} = \frac{2}{2} = 1$$

Let $P(k)$ be true for some positive integer $k$, i.e.,

$$1 + \frac{1}{{(1 + 2)}} + \frac{1}{{(1 + 2 + 3)}} + ... + \frac{1}{{(1 + 2 + 3 + ... + k)}} = \frac{{2k}}{{k + 1}}...(i)$$

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

Consider $$\begin{equation} \begin{aligned} \\ P(n):1 + \frac{1}{{(1 + 2)}} + \frac{1}{{(1 + 2 + 3)}} + ... + \frac{1}{{(1 + 2 + 3 + ... + n)}} = \frac{{2n}}{{n + 1}} \\ P(1):1 = \frac{{2.1}}{{1 + 1}} = \frac{2}{2} = 1 \\ 1 + \frac{1}{{(1 + 2)}} + \frac{1}{{(1 + 2 + 3)}} + ... + \frac{1}{{(1 + 2 + 3 + ... + k)}} = \frac{{2k}}{{k + 1}} \\ = 1 + \frac{1}{{(1 + 2)}} + \frac{1}{{(1 + 2 + 3)}} + ... + \frac{1}{{(1 + 2 + 3 + ... + k)}} + \frac{1}{{(1 + 2 + 3 + ... + k + (k + 1)}} \\ = (1 + \frac{1}{{(1 + 2)}} + \frac{1}{{(1 + 2 + 3)}} + ... + \frac{1}{{(1 + 2 + 3 + ... + k)}}) + \frac{1}{{(1 + 2 + 3 + ... + k + (k + 1)}} \\ = \frac{{2k}}{{k + 1}} + \frac{1}{{(1 + 2 + 3 + ... + k + (k + 1)}} \\ = \frac{{2k}}{{k + 1}} + (\frac{1}{{\frac{{(k + 1)(k + 1 + 1)}}{2}}}) \\ = \frac{{2k}}{{k + 1}} + \frac{2}{{(k + 1)(k + 2)}} \\ \frac{2}{{k + 1}}(k + \frac{1}{{k + 2}}) \\\end{aligned} \end{equation} $$

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

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