Chapter 2: Mathematical Induction

Problem 1

Prove that $\displaystyle 1 \cdot 3 + 2 \cdot 4 + 3 \cdot 5 + \cdots + (n - 1)(n + 1) = \frac{1}{6}(n - 1)n(2n + 5)$ for all natural numbers $\displaystyle n \ge 2$ by using principle of mathematical induction.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 1 \cdot 3 + 2 \cdot 4 + 3 \cdot 5 + \cdots + (n - 1)(n + 1) = \frac{1}{6}(n - 1)n(2n + 5)$.

(1) For $\displaystyle n = 2$,
$\displaystyle \text{LHS} = (2 - 1)(2 + 1) = 3$ and $\displaystyle \text{RHS} = \frac{1}{6}(2 - 1)(2)(2(2) + 5) = \frac{1}{6}(1)(2)(9) = 3$.
Since $\displaystyle \text{LHS} = \text{RHS}$, $\displaystyle P(2)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 2$, that is
$\displaystyle 1 \cdot 3 + 2 \cdot 4 + \cdots + (k - 1)(k + 1) = \frac{1}{6}(k - 1)k(2k + 5).$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 1 \cdot 3 + 2 \cdot 4 + \cdots + k(k + 2) = \frac{1}{6}k(k + 1)(2k + 7).$

The proof is as follows:

\displaystyle \begin{aligned} & 1 \cdot 3 + 2 \cdot 4 + \cdots + (k - 1)(k + 1) + k(k + 2) \\ & = \frac{1}{6}(k - 1)k(2k + 5) + k(k + 2) \\ & = \frac{k}{6} \left[ (k - 1)(2k + 5) + 6(k + 2) \right] \\ & = \frac{k}{6} \left[ 2k^2 + 3k - 5 + 6k + 12 \right] \\ & = \frac{k}{6} \left( 2k^2 + 9k + 7 \right) \\ & = \frac{1}{6}k(k + 1)(2k + 7) \end{aligned}

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 2

Prove that $\displaystyle 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + 3 \cdot 4 \cdot 5 + \cdots + n(n + 1)(n + 2) = \frac{1}{4}n(n + 1)(n + 2)(n + 3)$ for all natural numbers $\displaystyle n$ by using principle of mathematical induction.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + \cdots + n(n + 1)(n + 2) = \frac{1}{4}n(n + 1)(n + 2)(n + 3)$.

(1) For $\displaystyle n = 1$,
$\displaystyle \text{LHS} = 1(1 + 1)(1 + 2) = 6$ and $\displaystyle \text{RHS} = \frac{1}{4}(1)(1 + 1)(1 + 2)(1 + 3) = 6$.
Since $\displaystyle \text{LHS} = \text{RHS}$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + \cdots + k(k + 1)(k + 2) = \frac{1}{4}k(k + 1)(k + 2)(k + 3).$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 1 \cdot 2 \cdot 3 + \cdots + (k + 1)(k + 2)(k + 3) = \frac{1}{4}(k + 1)(k + 2)(k + 3)(k + 4).$

The proof is as follows:

\displaystyle \begin{aligned} & 1 \cdot 2 \cdot 3 + \cdots + k(k + 1)(k + 2) + (k + 1)(k + 2)(k + 3) \\ & = \frac{1}{4}k(k + 1)(k + 2)(k + 3) + (k + 1)(k + 2)(k + 3) \\ & = (k + 1)(k + 2)(k + 3) \left( \frac{k}{4} + 1 \right) \\ & = \frac{1}{4}(k + 1)(k + 2)(k + 3)(k + 4) \end{aligned}

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 3

Prove that $\displaystyle 1 \cdot 2 + 2 \cdot 2^2 + 3 \cdot 2^3 + \cdots + n \cdot 2^n = (n - 1)2^{n + 1} + 2$ for all natural numbers $\displaystyle n$ by using principle of mathematical induction.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 1 \cdot 2 + 2 \cdot 2^2 + \cdots + n \cdot 2^n = (n - 1)2^{n + 1} + 2$.

(1) For $\displaystyle n = 1$,
$\displaystyle \text{LHS} = 1 \cdot 2^1 = 2$ and $\displaystyle \text{RHS} = (1 - 1)2^{1 + 1} + 2 = 0 + 2 = 2$.
Since $\displaystyle \text{LHS} = \text{RHS}$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle 1 \cdot 2 + 2 \cdot 2^2 + \cdots + k \cdot 2^k = (k - 1)2^{k + 1} + 2.$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 1 \cdot 2 + 2 \cdot 2^2 + \cdots + (k + 1) \cdot 2^{k + 1} = k 2^{k + 2} + 2.$

The proof is as follows:

\displaystyle \begin{aligned} & 1 \cdot 2 + 2 \cdot 2^2 + \cdots + k \cdot 2^k + (k + 1) \cdot 2^{k + 1} \\ & = (k - 1)2^{k + 1} + 2 + (k + 1)2^{k + 1} \\ & = 2^{k + 1} (k - 1 + k + 1) + 2 \\ & = 2^{k + 1} (2k) + 2 \\ & = k 2^{k + 2} + 2 \end{aligned}

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 4

Prove, by mathematical induction, that for all natural numbers $\displaystyle n$,
$\displaystyle \sum_{r=1}^{n} r^2 = \frac{n(n + 1)(2n + 1)}{6}$

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle \sum_{r=1}^{n} r^2 = \frac{n(n + 1)(2n + 1)}{6}$.

(1) For $\displaystyle n = 1$,
$\displaystyle \text{LHS} = 1^2 = 1$ and $\displaystyle \text{RHS} = \frac{1(1 + 1)(2(1) + 1)}{6} = \frac{6}{6} = 1$.
Since $\displaystyle \text{LHS} = \text{RHS}$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle \sum_{r=1}^{k} r^2 = \frac{k(k + 1)(2k + 1)}{6}.$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle \sum_{r=1}^{k+1} r^2 = \frac{(k + 1)(k + 2)(2k + 3)}{6}.$

The proof is as follows:

\displaystyle \begin{aligned} & \sum_{r=1}^{k+1} r^2 \\ & = \sum_{r=1}^{k} r^2 + (k + 1)^2 \\ & = \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 \\ & = \frac{k + 1}{6} \left[ k(2k + 1) + 6(k + 1) \right] \\ & = \frac{k + 1}{6} \left( 2k^2 + 7k + 6 \right) \\ & = \frac{1}{6}(k + 1)(k + 2)(2k + 3) \end{aligned}

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 5

Prove that $\displaystyle 1^3 + 3^3 + 5^3 + \cdots + (2n - 1)^3 = n^2(2n^2 - 1)$ for all natural numbers $\displaystyle n$ by the use of the mathematical induction principle.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 1^3 + 3^3 + \cdots + (2n - 1)^3 = n^2(2n^2 - 1)$.

(1) For $\displaystyle n = 1$,
$\displaystyle \text{LHS} = 1^3 = 1$ and $\displaystyle \text{RHS} = 1^2(2(1)^2 - 1) = 1(1) = 1$.
Since $\displaystyle \text{LHS} = \text{RHS}$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle 1^3 + 3^3 + \cdots + (2k - 1)^3 = k^2(2k^2 - 1).$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 1^3 + 3^3 + \cdots + (2k + 1)^3 = (k + 1)^2(2(k + 1)^2 - 1).$

The proof is as follows:

\displaystyle \begin{aligned} & 1^3 + 3^3 + \cdots + (2k - 1)^3 + (2k + 1)^3 \\ & = k^2(2k^2 - 1) + (2k + 1)^3 \\ & = 2k^4 - k^2 + 8k^3 + 12k^2 + 6k + 1 \\ & = 2k^4 + 8k^3 + 11k^2 + 6k + 1 \\ & = (k^2 + 2k + 1)(2k^2 + 4k + 1) \\ & = (k + 1)^2 \left[ 2(k^2 + 2k + 1) - 1 \right] \\ & = (k + 1)^2(2(k + 1)^2 - 1) \end{aligned}

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 6

Show by the principle of mathematical induction that $\displaystyle 2^{2n - 1} + 5^{2n - 1} \text{ is divisible by } 7$ for all natural numbers $\displaystyle n$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 2^{2n - 1} + 5^{2n - 1} \text{ is divisible by } 7$.

(1) For $\displaystyle n = 1$,
$\displaystyle 2^{2(1) - 1} + 5^{2(1) - 1} = 2^1 + 5^1 = 7$ which is divisible by $\displaystyle 7$.
$\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle 2^{2k - 1} + 5^{2k - 1} \text{ is divisible by } 7.$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 2^{2(k + 1) - 1} + 5^{2(k + 1) - 1} \text{ is divisible by } 7.$

The proof is as follows:

\displaystyle \begin{aligned} & 2^{2(k + 1) - 1} + 5^{2(k + 1) - 1} \\ & = 2^{2k + 1} + 5^{2k + 1} \\ & = 2^2 \cdot 2^{2k - 1} + 5^2 \cdot 5^{2k - 1} \\ & = 4 \cdot 2^{2k - 1} + 25 \cdot 5^{2k - 1} \\ & = 4(2^{2k - 1} + 5^{2k - 1}) + 21 \cdot 5^{2k - 1} \end{aligned}

$\displaystyle 4(2^{2k - 1} + 5^{2k - 1})$ and $\displaystyle 21(5^{2k - 1})$ are divisible by $\displaystyle 7$.
Then $\displaystyle 4(2^{2k - 1} + 5^{2k - 1}) + 21 \cdot 5^{2k - 1} = 2^{2(k + 1) - 1} + 5^{2(k + 1) - 1}$ is also divisible by $\displaystyle 7$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 7

Prove that $\displaystyle 3^{2n} - 1 \text{ is divisible by } 8$ for all natural numbers $\displaystyle n \ge 1$ by using principle of mathematical induction.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 3^{2n} - 1 \text{ is divisible by } 8$.

(1) For $\displaystyle n = 1$,
$\displaystyle 3^{2(1)} - 1 = 9 - 1 = 8$ which is divisible by $\displaystyle 8$.
$\displaystyle \therefore \quad P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 1$, that is
$\displaystyle 3^{2k} - 1 \text{ is divisible by } 8.$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 3^{2(k + 1)} - 1 \text{ is divisible by } 8.$

The proof is as follows:

\displaystyle \begin{aligned} & 3^{2(k + 1)} - 1 \\ & = 3^{2k + 2} - 1 \\ & = 9 \cdot 3^{2k} - 1 \\ & = 9(3^{2k} - 1) + 8 \end{aligned}

$\displaystyle 9(3^{2k} - 1)$ and $\displaystyle 8$ are divisible by $\displaystyle 8$.
Then $\displaystyle 9(3^{2k} - 1) + 8 = 3^{2(k + 1)} - 1$ is also divisible by $\displaystyle 8$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 8

Prove that $\displaystyle 2n < 2^n$ for all natural numbers $\displaystyle n \ge 3$ by using the mathematical induction.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 2n < 2^n$.

(1) For $\displaystyle n = 3$,
$\displaystyle \text{LHS} = 2(3) = 6$ and $\displaystyle \text{RHS} = 2^3 = 8$.
Since $\displaystyle 6 < 8$, $\displaystyle P(3)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 3$, that is
$\displaystyle 2k < 2^k.$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 2(k + 1) < 2^{k + 1}.$

The proof is as follows:

\displaystyle \begin{aligned} & 2(k + 1) \\ & = 2k + 2 \\ & < 2^k + 2 \quad (\text{since } 2k < 2^k) \\ & < 2^k + 2^k \quad (\text{since } 2 < 2^k \text{ for } k \ge 3) \\ & = 2 \cdot 2^k \\ & = 2^{k + 1} \end{aligned}

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 9

Use the mathematical induction principle to prove that $\displaystyle 2n + 1 < n^2$ for all natural numbers $\displaystyle n \ge 3$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 2n + 1 < n^2$.

(1) For $\displaystyle n = 3$,
$\displaystyle \text{LHS} = 2(3) + 1 = 7$ and $\displaystyle \text{RHS} = 3^2 = 9$.
Since $\displaystyle 7 < 9$, $\displaystyle P(3)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 3$, that is
$\displaystyle 2k + 1 < k^2.$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 2(k + 1) + 1 < (k + 1)^2.$

The proof is as follows:

\displaystyle \begin{aligned} & 2(k + 1) + 1 \\ & = (2k + 1) + 2 \\ & < k^2 + 2 \quad (\text{since } 2k + 1 < k^2) \\ & < k^2 + 2k + 1 \quad (\text{since } 2 < 2k + 1 \text{ for } k \ge 3) \\ & = (k + 1)^2 \end{aligned}

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 10

Use the mathematical induction principle to prove that $\displaystyle 1 + 5 + 9 + \cdots + (4n - 3) = 2n^2 - n$ for all natural numbers $\displaystyle n$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 1 + 5 + 9 + \cdots + (4n - 3) = 2n^2 - n$.

(1) For $\displaystyle n = 1$,
$\displaystyle \text{LHS} = 1$ and $\displaystyle \text{RHS} = 2(1)^2 - 1 = 1$.
Since $\displaystyle \text{LHS} = \text{RHS}$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle 1 + 5 + 9 + \cdots + (4k - 3) = 2k^2 - k.$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 1 + 5 + 9 + \cdots + (4k + 1) = 2(k + 1)^2 - (k + 1).$

The proof is as follows:

\displaystyle \begin{aligned} & 1 + 5 + 9 + \cdots + (4k - 3) + (4k + 1) \\ & = 2k^2 - k + 4k + 1 \\ & = 2k^2 + 3k + 1 \\ & = 2(k^2 + 2k + 1) - k - 1 \\ & = 2(k + 1)^2 - (k + 1) \end{aligned}

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 11

Prove that $\displaystyle n^3 + 2n \text{ is divisible by } 3$ for all natural numbers $\displaystyle n$ by using the mathematical induction.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle n^3 + 2n \text{ is divisible by } 3$.

(1) For $\displaystyle n = 1$,
$\displaystyle 1^3 + 2(1) = 3$ which is divisible by $\displaystyle 3$.
$\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle k^3 + 2k \text{ is divisible by } 3.$
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle (k + 1)^3 + 2(k + 1) \text{ is divisible by } 3.$

The proof is as follows:

\displaystyle \begin{aligned} & (k + 1)^3 + 2(k + 1) \\ & = k^3 + 3k^2 + 3k + 1 + 2k + 2 \\ & = k^3 + 2k + 3k^2 + 3k + 3 \\ & = (k^3 + 2k) + 3(k^2 + k + 1) \end{aligned}

$\displaystyle (k^3 + 2k)$ and $\displaystyle 3(k^2 + k + 1)$ are divisible by $\displaystyle 3$.
Then $\displaystyle (k^3 + 2k) + 3(k^2 + k + 1) = (k + 1)^3 + 2(k + 1)$ is also divisible by $\displaystyle 3$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 12

Use the mathematical induction principle to prove that $\displaystyle n! > 2^n$ for all natural numbers $\displaystyle n \ge 4$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle n! > 2^n$.

(1) For $\displaystyle n = 4$,
$\displaystyle \text{LHS} = 4! = 24$ and $\displaystyle \text{RHS} = 2^4 = 16$.
Since $\displaystyle 24 > 16$, $\displaystyle P(4)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 4$, that is
$\displaystyle k! > 2^k$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle (k + 1)! > 2^{k + 1}$.

The proof is as follows:

\displaystyle \begin{aligned} & (k + 1)! \\ & = (k + 1) \cdot k! \\ & > (k + 1) \cdot 2^k \quad (\text{since } k! > 2^k) \end{aligned}

Since $\displaystyle k \ge 4$, we have $\displaystyle k + 1 \ge 5 > 2$.

Therefore,

\displaystyle \begin{aligned} & (k + 1) \cdot 2^k \\ & > 2 \cdot 2^k \\ & = 2^{k + 1} \end{aligned}

Thus, $\displaystyle (k + 1)! > 2^{k + 1}$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 13

Use the mathematical induction principle to prove that $\displaystyle 2^n > n^2$ for all natural numbers $\displaystyle n \ge 5$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 2^n > n^2$.

(1) For $\displaystyle n = 5$,
$\displaystyle \text{LHS} = 2^5 = 32$ and $\displaystyle \text{RHS} = 5^2 = 25$.
Since $\displaystyle 32 > 25$, $\displaystyle P(5)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 5$, that is
$\displaystyle 2^k > k^2$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 2^{k + 1} > (k + 1)^2$.

The proof is as follows:

\displaystyle \begin{aligned} & 2^{k + 1} \\ & = 2 \cdot 2^k \\ & > 2 \cdot k^2 \quad (\text{since } 2^k > k^2) \\ & = k^2 + k^2 \end{aligned}

Since $\displaystyle k \ge 5$, we have $\displaystyle k^2 \ge 5k = 2k + 3k > 2k + 1$.

Therefore,

\displaystyle \begin{aligned} & k^2 + k^2 \\ & > k^2 + 2k + 1 \\ & = (k + 1)^2 \end{aligned}

Thus, $\displaystyle 2^{k + 1} > (k + 1)^2$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 14

Use the mathematical induction principle to prove that $\displaystyle (1 + x)^n \ge 1 + nx$ for all $\displaystyle n \in \mathbb{N}$ and $\displaystyle x > -1$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle (1 + x)^n \ge 1 + nx$.

(1) For $\displaystyle n = 1$,
$\displaystyle \text{LHS} = (1 + x)^1 = 1 + x$ and $\displaystyle \text{RHS} = 1 + 1 \cdot x = 1 + x$.
Since $\displaystyle 1 + x \ge 1 + x$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle (1 + x)^k \ge 1 + kx$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle (1 + x)^{k + 1} \ge 1 + (k + 1)x$.

The proof is as follows:

Since $\displaystyle x > -1$, we have $\displaystyle 1 + x > 0$. Multiplying both sides of the assumption by $\displaystyle (1 + x)$:

\displaystyle \begin{aligned} & (1 + x)^{k + 1} \\ & = (1 + x)^k (1 + x) \\ & \ge (1 + kx)(1 + x) \quad (\text{since } (1+x)^k \ge 1+kx \text{ and } 1+x > 0) \\ & = 1 + x + kx + kx^2 \\ & = 1 + (k + 1)x + kx^2 \end{aligned}

Since $\displaystyle k \ge 1$ and $\displaystyle x^2 \ge 0$, we have $\displaystyle kx^2 \ge 0$.

$\displaystyle 1 + (k + 1)x + kx^2 \ge 1 + (k + 1)x$.

Thus, $\displaystyle (1 + x)^{k + 1} \ge 1 + (k + 1)x$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 15

Given that the sequence of real numbers defined by the relations $\displaystyle x_1 = \sqrt{2}$ and $\displaystyle x_{n+1} = \sqrt{2 + x_n}$ for $\displaystyle n \ge 1$. Prove by mathematical induction that $\displaystyle x_n < 2$ for all $\displaystyle n \ge 1$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle x_n < 2$.

(1) For $\displaystyle n = 1$,
$\displaystyle x_1 = \sqrt{2} \approx 1.414$.
Since $\displaystyle \sqrt{2} < 2$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle x_k < 2$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle x_{k + 1} < 2$.

The proof is as follows:

\displaystyle \begin{aligned} & x_{k + 1} \\ & = \sqrt{2 + x_k} \\ & < \sqrt{2 + 2} \quad (\text{since } x_k < 2) \\ & = \sqrt{4} \\ & = 2 \end{aligned}

Thus, $\displaystyle x_{k + 1} < 2$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 16

Given that the sequence of real numbers defined by the relations $\displaystyle x_1 = 1$ and $\displaystyle x_{n+1} = \sqrt{6 + x_n}$ for $\displaystyle n \ge 1$. Prove by mathematical induction that $\displaystyle x_n < 3$ for all $\displaystyle n \ge 1$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle x_n < 3$.

(1) For $\displaystyle n = 1$, $\displaystyle x_1 = 1$.
Since $\displaystyle 1 < 3$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle x_k < 3$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle x_{k + 1} < 3$.

The proof is as follows:

\displaystyle \begin{aligned} & x_{k + 1} \\ & = \sqrt{6 + x_k} \\ & < \sqrt{6 + 3} \quad (\text{since } x_k < 3) \\ & = \sqrt{9} \\ & = 3 \end{aligned}

Thus, $\displaystyle x_{k + 1} < 3$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 17

Given that the sequence of real numbers defined by the relations $\displaystyle x_1 = 2$ and $\displaystyle x_{n+1} = \sqrt{3x_n + 4}$ for $\displaystyle n \ge 1$. Prove by mathematical induction that $\displaystyle x_n < 4$ for all $\displaystyle n \ge 1$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle x_n < 4$.

(1) For $\displaystyle n = 1$, $\displaystyle x_1 = 2$.
Since $\displaystyle 2 < 4$, $\displaystyle P(1)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}$, that is
$\displaystyle x_k < 4$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle x_{k + 1} < 4$.

The proof is as follows:

\displaystyle \begin{aligned} & x_{k + 1} \\ & = \sqrt{3x_k + 4} \\ & < \sqrt{3(4) + 4} \quad (\text{since } x_k < 4) \\ & = \sqrt{12 + 4} \\ & = \sqrt{16} \\ & = 4 \end{aligned}

Thus, $\displaystyle x_{k + 1} < 4$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 18

Use the mathematical induction principle to prove that $\displaystyle 3n < 3^n - 2$ for all natural numbers $\displaystyle n \ge 2$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 3n < 3^n - 2$.

(1) For $\displaystyle n = 2$,
$\displaystyle \text{LHS} = 3(2) = 6$ and $\displaystyle \text{RHS} = 3^2 - 2 = 9 - 2 = 7$.
Since $\displaystyle 6 < 7$, $\displaystyle P(2)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 2$, that is
$\displaystyle 3k < 3^k - 2$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 3(k + 1) < 3^{k + 1} - 2$.

The proof is as follows:

\displaystyle \begin{aligned} & 3(k + 1) \\ & = 3k + 3 \\ & < (3^k - 2) + 3 \quad (\text{since } 3k < 3^k - 2) \\ & = 3^k + 1 \end{aligned}

We need to show that $\displaystyle 3^k + 1 \le 3^{k + 1} - 2$.

\displaystyle \begin{aligned} & 3^{k + 1} - 2 \\ & = 3 \cdot 3^k - 2 \\ & = 3^k + 2 \cdot 3^k - 2 \\ & \ge 3^k + 18 - 2 \quad (\text{since } 2 \cdot 3^k \ge 18 \text{ for } k \ge 2) \\ & = 3^k + 16 \\ & > 3^k + 1 \end{aligned}

$\displaystyle 3(k + 1) < 3^k + 1 < 3^{k + 1} - 2$.

Thus, $\displaystyle 3(k + 1) < 3^{k + 1} - 2$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 19

Use the mathematical induction principle to prove that $\displaystyle 2n + 1 < 2^n$ for all natural numbers $\displaystyle n \ge 3$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 2n + 1 < 2^n$.

(1) For $\displaystyle n = 3$,
$\displaystyle \text{LHS} = 2(3) + 1 = 7$ and $\displaystyle \text{RHS} = 2^3 = 8$.
Since $\displaystyle 7 < 8$, $\displaystyle P(3)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 3$, that is
$\displaystyle 2k + 1 < 2^k$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 2(k + 1) + 1 < 2^{k + 1}$.

The proof is as follows:

\displaystyle \begin{aligned} & 2(k + 1) + 1 \\ & = (2k + 1) + 2 \\ & < 2^k + 2 \quad (\text{since } 2k + 1 < 2^k) \end{aligned}

Since $\displaystyle k \ge 3$, we have $\displaystyle 2 < 2^3 = 8 \le 2^k$.

Therefore,

\displaystyle \begin{aligned} & 2^k + 2 \\ & < 2^k + 2^k \quad (\text{since } 2 < 2^k \text{ for } k \ge 3) \\ & = 2 \cdot 2^k \\ & = 2^{k + 1} \end{aligned}

Thus, $\displaystyle 2(k + 1) + 1 < 2^{k + 1}$.

Therefore, $\displaystyle P(k + 1)$ is true.

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

Problem 20

Use the mathematical induction principle to prove that $\displaystyle 4n < 2^n$ for all natural numbers $\displaystyle n \ge 5$.

Show Solution

Let $\displaystyle P(n)$ denote the statement $\displaystyle 4n < 2^n$.

(1) For $\displaystyle n = 5$,
$\displaystyle \text{LHS} = 4(5) = 20$ and $\displaystyle \text{RHS} = 2^5 = 32$.
Since $\displaystyle 20 < 32$, $\displaystyle P(5)$ is true.

(2) Assume $\displaystyle P(k)$ is true for some $\displaystyle k \in \mathbb{N}, k \ge 5$, that is
$\displaystyle 4k < 2^k$.
We will show that $\displaystyle P(k + 1)$ is true, that is:
$\displaystyle 4(k + 1) < 2^{k + 1}$.

The proof is as follows:

\displaystyle \begin{aligned} & 4(k + 1) \\ & = 4k + 4 \\ & < 2^k + 4 \quad (\text{since } 4k < 2^k) \end{aligned}

Since $\displaystyle k \ge 5$, we have $\displaystyle 4 < 2^5 = 32 \le 2^k$.

Therefore,

\displaystyle \begin{aligned} & 2^k + 4 \\ & < 2^k + 2^k \quad (\text{since } 4 < 2^k \text{ for } k \ge 5) \\ & = 2 \cdot 2^k \\ & = 2^{k + 1} \end{aligned}

Thus, $\displaystyle 4(k + 1) < 2^{k + 1}$.

Therefore, $\displaystyle P(k + 1)$ is true.

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