$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.5: More on Mathematical Induction

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Besides identities, we can also use mathematical induction to prove a statement about a positive integer $$n$$.

Example $$\PageIndex{1}\label{eg:inductmultsix}$$

Prove that $$n(n+1)(2n+1)$$ is a multiple of 6 for all integers $$n\geq1$$.

Remark

We have already seen how to prove this claim using a proof by cases, which is actually an easier way to prove that $$n(n+1)(2n+1)$$ is divisible by 6. Nonetheless, we shall demonstrate below how to use induction to prove the claim.

Discussion

In the inductive hypothesis, it is clear that we are assuming $$k(k+1)(2k+1)$$ is a multiple of 6. In the inductive step, we want to prove that $(k+1)(k+2)[2(k+1)+1] = (k+1)(k+2)(2k+3) \nonumber$ is also a multiple of 6. A multiple of 6 can be written as $$6q$$ for some integer $$q$$. Since we have two multiples of 6, we need to write $k(k+1)(2k+1) = 6q \nonumber$ and $(k+1)(k+2)(2k+3) = 6Q \nonumber$ to distinguish them. By using the lowercase and uppercase of the same letter, we indicate that they are different values. Yet, because they come from the same letter, they both share some common attribute, in this case, being the quotients when the respective values are divided by 6.

Now, in the inductive step, we need to make use of the equation $$k(k+1)(2k+1)=6q$$ from the inductive hypothesis. This calls for connecting the product $$(k+1)(k+2)(2k+3)$$ to the expression $$k(k+1)(2k+1)$$. Since they share the common factor $$k+1$$, what remains to do is write $$(k+2)(2k+3)$$ in terms of $$k(2k+1)$$.

We are asked to prove that $$n(n+1)(2n+1)$$ is a multiple of 6. This is not an identity. Therefore, do not say “assume/show that the identity holds when … .” Instead, say “assume/show that the claim is true when … .”

Solution

Proceed by induction on $$n$$. When $$n=1$$, we have $$n(n+1)(2n+1)= 1\cdot2\cdot3=6$$, which is clearly a multiple of 6. Hence, the claim is true when $$n=1$$. Assume the claim is true when $$n=k$$ for some integer $$k\geq1$$; that is, assume that we can write $k(k+1)(2k+1) = 6q\nonumber$ for some integer $$q$$. We want to show that the claim is still true when $$n=k+1$$; that is, we want to show that $(k+1)(k+2)[2(k+1)+1] = (k+1)(k+2)(2k+3) = 6Q\nonumber$ for some integer $$Q$$. Using the inductive hypothesis, we find $\begin{array}{r c l} (k+1)(k+2)(2k+3) &=& (k+1)(2k^2+7k+6) \\ &=& (k+1)[(2k^2+k)+(6k+6)] \\ &=& (k+1)[k(2k+1)+6(k+1)] \\ &=& k(k+1)(2k+1) + 6(k+1)^2 \\ &=& 6q + 6(k+1)^2 \\ &=& 6\,[q+(k+1)^2], \end{array} \nonumber$ where $$q+(k+1)^2$$ is clearly an integer. This completes the induction.

hands-on exercise $$\PageIndex{1}\label{he:induct2-01}$$

Prove that $$n^2+3n+2$$ is even for all integers $$n\geq1$$.

Induction can also be used to prove inequalities, which often require more work to finish.

Example $$\PageIndex{2}\label{eg:induct2-02}$$

Prove that $1+\frac{1}{4}+\cdots+\frac{1}{n^2} \leq 2-\frac{1}{n} \nonumber$ for all positive integers $$n$$.

Draft. In the inductive hypothesis, we assume that the inequality holds when $$n=k$$ for some integer $$k\geq1$$. This means we assume $\sum_{i=1}^k \frac{1}{i^2} \leq 2-\frac{1}{k}. \nonumber$ In the inductive step, we want to show that it also holds when $$n=k+1$$. In other words, we want to prove that $\sum_{i=1}^{k+1} \frac{1}{i^2} \leq 2-\frac{1}{k+1}. \nonumber$

In order to use the inductive hypothesis, we have to find a connection between these two inequalities. Obviously, we have $\sum_{i=1}^{k+1} \frac{1}{i^2} = \left(\sum_{i=1}^k \frac{1}{i^2}\right) + \frac{1}{(k+1)^2}. \nonumber$ Hence, it follows from the inductive hypothesis that $\sum_{i=1}^{k+1} \frac{1}{i^2} = \left(\sum_{i=1}^k \frac{1}{i^2}\right) + \frac{1}{(k+1)^2} \leq 2-\frac{1}{k} + \frac{1}{(k+1)^2}. \nonumber$ The proof would be complete if we could show that $2-\frac{1}{k} + \frac{1}{(k+1)^2} \leq 2-\frac{1}{k+1}. \nonumber$ There is no guarantee that this idea will work, but this should be the first thing we try.

After rearrangement, the inequality becomes $\frac{1}{k+1}+\frac{1}{(k+1)^2} \leq \frac{1}{k}, \nonumber$ which is equivalent to $$\frac{k+2}{(k+1)^2} \leq \frac{1}{k}$$. Cross-multiplication yields $k(k+2) \leq (k+1)^2. \nonumber$ Since $k(k+2)=k^2+2k, \qquad\mbox{and}\qquad (k+1)^2=k^2+2k+1, \nonumber$ it is clear that what we want to prove is indeed true.

Polish It Up! Next, we rearrange the argument to make it read more smoothly. Essentially all we need is to run the argument backward. To improve the flow of the argument, we can prove a separate result on the side before we return to the main argument.

Proof 1

Proceed by induction on $$n$$. When $$n=1$$, the left-hand side becomes 1, and so does the right-hand side; thus, the inequality holds. Assume it holds when $$n=k$$ for some integer $$k\geq1$$: $\sum_{i=1}^k \frac{1}{i^2} \leq 2-\frac{1}{k}. \nonumber$ We want to show that it also holds when $$n=k+1$$: $\sum_{i=1}^{k+1} \frac{1}{i^2} \leq 2-\frac{1}{k+1}. \nonumber$

To finish the proof, we need to derive an inequality. Notice that $k(k+2) = k^2+2k < k^2+2k+1 = (k+1)^2. \nonumber$ Hence, after dividing both sides by $$k(k+1)^2$$, we obtain $\frac{k+2}{(k+1)^2} < \frac{1}{k}. \nonumber$ This leads to $\frac{1}{k+1} + \frac{1}{(k+1)^2} = \frac{(k+1)+1}{(k+1)^2} = \frac{k+2}{(k+1)^2} < \frac{1}{k}, \nonumber$ which is equivalent to $-\frac{1}{k} + \frac{1}{(k+1)^2} < -\frac{1}{k+1}. \label{eq:induct2-ineq} \nonumber$

We now return to our original problem. It follows from the inductive hypothesis and ([eq:induct2-ineq]) that $\begin{array}{r c l} \sum_{i=1}^{k+1} \frac{1}{i^2} &=& \left(\sum_{i=1}^k \frac{1}{i^2}\right) +\frac{1}{(k+1)^2} \\ &\leq& 2-\frac{1}{k} + \frac{1}{(k+1)^2} \\ & < & 2-\frac{1}{k+1}. \end{array} \nonumber$ Therefore, the inequality still holds when $$n=k+1$$, which completes the induction.

Remark

The key step in the proof is to establish ([eq:induct2-ineq]), which can be done by means of contradiction.

Proof 2

Proceed by induction on $$n$$. When $$n=1$$, the left-hand side becomes 1, and so does the right-hand side; thus, the inequality holds. Assume it holds when $$n=k$$ for some integer $$k\geq1$$: $\sum_{i=1}^k \frac{1}{i^2} \leq 2-\frac{1}{k}. \nonumber$ We want to show that it also holds when $$n=k+1$$: $\sum_{i=1}^{k+1} \frac{1}{i^2} \leq 2-\frac{1}{k+1}. \nonumber$

To finish the proof, we need the following inequality. We claim that $-\frac{1}{k} + \frac{1}{(k+1)^2} < -\frac{1}{k+1}. \label{eq:induct2-ineqalt}\nonumber$ Suppose, on the contrary, that $-\frac{1}{k} + \frac{1}{(k+1)^2} \geq -\frac{1}{k+1}.\nonumber$ Clear the denominators by multiplying $$k(k+1)^2$$ to both sides of the inequality. We find $-(k+1)^2 + k \geq -k(k+1),\nonumber$ or equivalently, $-k^2-k-1 \geq -k^2-k,\nonumber$ which is the same as saying $$-1\geq0$$. This contradiction proves that ([eq:induct2-ineqalt]) must be true.

We now return to our original problem. It follows from the inductive hypothesis and ([eq:induct2-ineqalt]) that $\begin{array}{r c l} \sum_{i=1}^{k+1} \frac{1}{i^2} &=& \left(\sum_{i=1}^k \frac{1}{i^2}\right) +\frac{1}{(k+1)^2} \\ &\leq& 2-\frac{1}{k} + \frac{1}{(k+1)^2} \\ & < & 2-\frac{1}{k+1}. \end{array} \nonumber$ Therefore, the inequality still holds when $$n=k+1$$, which completes the induction.

hands-on exercise $$\PageIndex{2}\label{he:induct2-02}$$

Show that $$n < 2^n$$ for all integers $$n\geq1$$.

We do not have to start with $$n=1$$ in the basis step. We can start with any integer $$n_0$$.

Generalization. To show that $$P(n)$$ is true for all integers $$n \geq n_0$$, follow these steps:

1. Verify that $$P(n_0)$$ is true.
2. Assume that $$P(k)$$ is true for some integer $$k\geq n_0$$.
3. Show that $$P(k+1)$$ is also true.

The major difference is in the basis step: we need to verify that $$P(n_0)$$ is true. In addition, in the inductive hypothesis, we need to stress that $$k\geq n_0$$.

Example $$\PageIndex{3}\label{eg:induct2-03}$$

Use mathematical induction to show that $\sum_{i=0}^n 4^i = \frac{1}{3} (4^{n+1}-1) \nonumber$ for all integers $$n\geq0$$.

Solution

Proceed by induction on $$n$$. When $$n=0$$, the left-hand side reduces to $$\sum_{i=0}^0 4^i = 4^0 = 1$$, and the right-hand side becomes $$\frac{1}{3} (4^1-1) = \frac{1}{3}\cdot3 = 1$$. Hence, the formula holds when $$n=0$$. Assume it holds when $$n=k$$ for some integer $$k\geq0$$; that is, assume $\sum_{i=0}^k 4^i = \frac{1}{3} (4^{k+1}-1). \nonumber$ We want to show that it also holds when $$n=k+1$$; that is, $\sum_{i=0}^{k+1} 4^i = \frac{1}{3} (4^{k+2}-1). \nonumber$ Using the inductive hypothesis, we find $\begin{array}{r c l} \sum_{i=0}^{k+1} 4^i &=& \left(\sum_{i=0}^k 4^i\right) + 4^{k+1} \\ &=& \textstyle\frac{1}{3}\,(4^{k+1}-1) + 4^{k+1} \\ &=& \textstyle\frac{1}{3}\,(4^{k+1}-1+3\cdot4^{k+1}) \\ &=& \textstyle\frac{1}{3}\,(4\cdot4^{k+1}-1) \\ &=& \textstyle\frac{1}{3}\,(4^{k+2}-1), \end{array} \nonumber$ which is what we want to prove, thereby completing the induction.

hands-on exercise $$\PageIndex{3}\label{he:induct2-03}$$

Prove that, for any integer $$n\geq0$$, $1+\frac{2}{3}+\frac{4}{9}+\cdots+\left(\frac{2}{3}\right)^n = 3\,\left[1-\left(\frac{2}{3}\right)^{n+1}\right]. \nonumber$

Example $$\PageIndex{4}\label{eg:induct2-04}$$

Use mathematical induction to show that $n^n \geq 2^n \nonumber$ for all integers $$n\geq2$$.

Solution

Proceed by induction on $$n$$. When $$n=2$$, the inequality becomes $$2^2\geq 2^2$$, which is obviously true. Assume it holds when $$n=k$$ for some integer $$k\geq2$$: $k^k \geq 2^k. \nonumber$ We want to show that it still holds when $$n=k+1$$: $(k+1)^{k+1} \geq 2^{k+1}. \nonumber$ Since $$k\geq2$$, it follows from the inductive hypothesis that $(k+1)^{k+1} \geq k^{k+1} = k\cdot k^k \geq 2\cdot 2^k = 2^{k+1}. \nonumber$ Therefore, the inequality still holds when $$n=k+1$$. This completes the induction.

## Summary and Review

• We can use induction to prove a general statement involving an integer $$n$$.
• The statement can be an identity, an inequality, or a claim about the property of an expression involving $$n$$.
• An induction proof need not start with $$n=1$$.
• If we want to prove that a statement is true for all integers $$n\geq n_0$$, we have to verify the statement for $$n=n_0$$ in the basis step.
• In addition, we need to assume that $$k\geq n_0$$ in the inductive hypothesis.

## Exercises 3.5

Exercise $$\PageIndex{1}\label{ex:induct2-01}$$

Use induction to prove that $$n(n+1)(n+2)$$ is a multiple of 3 for all integers $$n\geq1$$.

Exercise $$\PageIndex{2}\label{ex:induct2-02}$$

Use induction to show that $$n^3+5n$$ is a multiple of 6 for any nonnegative integer $$n$$.

Exercise $$\PageIndex{3}\label{ex:induct2-03}$$

Use induction to prove that $2+\left(1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}} +\cdots+\frac{1}{\sqrt{n}}\right) > 2\sqrt{n+1} \nonumber$ for all integers $$n\geq1$$.

Exercise $$\PageIndex{4}\label{ex:induct2-04}$$

Use induction to prove that $2\left(1+\frac{1}{8}+\frac{1}{27} +\cdots+\frac{1}{n^3}\right) \leq 3-\frac{1}{n^2} \nonumber$ for all integers $$n\geq1$$.

Exercise $$\PageIndex{5}\label{ex:induct2-05}$$

Use induction to prove that $a+ar+ar^2+\cdots+ar^n = \frac{a(r^{n+1}-1)}{r-1} \nonumber$ for all nonnegative integers $$n$$, where $$a$$ and $$r$$ are real numbers with $$r\neq1$$.

Exercise $$\PageIndex{6}\label{ex:induct2-06}$$

Use induction to prove that, for any integer $$n\geq2$$, $6 \sum_{i=2}^n i(i+2) = 2n^3+9n^2+7n-18. \nonumber$

Exercise $$\PageIndex{7}\label{ex:induct2-07}$$

Use induction to prove that, for any integer $$n\geq0$$, $1-\frac{2}{5}+\frac{4}{25}+\cdots+\left(-\frac{2}{5}\right)^n = \frac{5}{7}\,\left[1-\left(-\frac{2}{5}\right)^{n+1}\right]. \nonumber$

Exercise $$\PageIndex{8}\label{ex:induct2-08}$$

Use induction to show that $$n!>2^n$$ for all integers $$n\geq4$$.

Exercise $$\PageIndex{9}\label{ex:induct2-09}$$

Use induction to prove that $$n^2>4n+1$$ for all integers $$n\geq5$$.

Exercise $$\PageIndex{10}\label{ex:induct2-10}$$

Prove that $$2n+1 < 2^n$$ for all integers $$n\geq3$$.

Exercise $$\PageIndex{11}\label{ex:induct2-11}$$

Define $S_n = \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{n}{(n+1)!}. \nonumber$

1. Evaluate $$S_n$$ for $$n=1,2,3,4,5$$.
2. Propose a simple formula for $$S_n$$.
3. Use induction to prove your conjecture for all integers $$n\geq1$$.

Exercise $$\PageIndex{12}\label{ex:induct2-12}$$

Define $$T_n = \sum_{i=0}^n \frac{1}{(2i+1)(2i+3)}$$.

1. Evaluate $$T_n$$ for $$n=0,1,2,3,4$$.
2. Propose a simple formula for $$T_n$$.
3. Use induction to prove your conjecture for all integers $$n\geq0$$.