$$\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.4: Mathematical Induction - An Introduction

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Mathematical induction can be used to prove that an identity is valid for all integers $$n\geq1$$. Here is a typical example of such an identity: $1+2+3+\cdots+n = \frac{n(n+1)}{2}.$ More generally, we can use mathematical induction to prove that a propositional function $$P(n)$$ is true for all integers $$n\geq1$$.

Definition: Mathematical Induction

To show that a propositional function $$P(n)$$ is true for all integers $$n\geq1$$, follow these steps:

• Basis Step: Verify that $$P(1)$$ is true.
• Inductive Step: Show that if $$P(k)$$ is true for some integer $$k\geq1$$, then $$P(k+1)$$ is also true.

The basis step is also called the anchor step or the initial step. This proof technique is valid because of the next theorem.

Theorem $$\PageIndex{1}\label{thm:pmi}$$: Principle of Mathematical Induction

If $$S \subseteq \mathbb{N}$$ such that

• $$1\in S$$, and
• $$k\in S \Rightarrow k+1\in S$$,

then $$S=\mathbb{N}$$.

Remark

Here is a sketch of the proof. From (i), we know that $$1\in S$$. It then follows from (ii) that $$2\in S$$. Applying (ii) again, we find that $$3\in S$$. Likewise, $$4\in S$$, then $$5\in S$$, and so on. Since this argument can go on indefinitely, we find that $$S = \mathbb{N}$$.

There is a subtle problem with this argument. It is unclear why “and so on” will work. After all, what does “and so on” or “continue in this manner” really mean? Can it really continue indefinitely? The trouble is, we do not have a formal definition of the natural numbers. It turns out that we cannot completely prove the principle of mathematical induction with just the usual properties for addition and multiplication. Consequently, we will take the theorem as an axiom without giving any formal proof.

Although we cannot provide a satisfactory proof of the principle of mathematical induction, we can use it to justify the validity of the mathematical induction. Let $$S$$ be the set of integers $$n$$ for which a propositional function $$P(n)$$ is true. The basis step of mathematical induction verifies that $$1\in S$$. The inductive step shows that $$k\in S$$ implies $$k+1\in S$$. Therefore, the principle of mathematical induction proves that $$S=\mathbb{N}$$. It follows that $$P(n)$$ is true for all integers $$n\geq1$$.

The basis step and the inductive step, together, prove that $P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots\,.$ Therefore, $$P(n)$$ is true for all integers $$n\geq1$$. Compare induction to falling dominoes. When the first domino falls, it knocks down the next domino. The second domino in turn knocks down the third domino. Eventually, all the dominoes will be knocked down. But it will not happen unless these conditions are met:

• The first domino must fall to start the motion. If it does not fall, no chain reaction will occur. This is the basis step.
• The distance between adjacent dominoes must be set up correctly. Otherwise, a certain domino may fall down without knocking over the next. Then the chain reaction will stop, and will never be completed. Maintaining the right inter-domino distance ensures that $$P(k)\Rightarrow P(k+1)$$ for each integer $$k\geq1$$.

To prove the implication $P(k) \Rightarrow P(k+1)$ in the inductive step, we need to carry out two steps: assuming that $$P(k)$$ is true, then using it to prove $$P(k+1)$$ is also true. So we can refine an induction proof into a 3-step procedure:

• Verify that $$P(1)$$ is true.
• Assume that $$P(k)$$ is true for some integer $$k\geq1$$.
• Show that $$P(k+1)$$ is also true.

The second step, the assumption that $$P(k)$$ is true, is sometimes referred to as the inductive hypothesis or induction hypothesis. This is how a mathematical induction proof may look:

The idea behind mathematical induction is rather simple. However, it must be delivered with precision.

• Be sure to say “Assume the identity holds for some integer $$k\geq1$$.” Do not say “Assume it holds for all integers $$k\geq1$$.” If we already know the result holds for all $$k\geq1$$, then there is no need to prove anything at all.
• Be sure to specify the requirement $$k\geq1$$. This ensures that the chain reaction of the falling dominoes starts with the first one.
• Do not say “let $$n=k$$” or “let $$n=k+1$$.” The point is, you are not assigning the value of $$k$$ and $$k+1$$ to $$n$$. Rather, you are assuming that the statement is true when $$n$$ equals $$k$$, and using it to show that the statement also holds when $$n$$ equals $$k+1$$.

Example $$\PageIndex{1}\label{eg:induct1-01}$$

Use mathematical induction to show that $1+2+3+\cdots+n = \frac{n(n+1)}{2}$ for all integers $$n\geq1$$.

Discussion

In the basis step, it would be easier to check the two sides of the equation separately. The inductive step is the key step in any induction proof, and the last part, the part that proves $$P(k+1)$$ is true, is the most difficult part of the entire proof. In this regard, it is helpful to write out exactly what the inductive hypothesis proclaims, and what we really want to prove. In this problem, the inductive hypothesis claims that

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

We want to prove that $$P(k+1)$$ is also true. What does $$P(k+1)$$ really mean? It says

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

Compare the left-hand sides of these two equations. The first one is the sum of $$k$$ quantities, and the second is the sum of $$k+1$$ quantities, and the extra quantity is the last number $$k+1$$. The sum of the first $$k$$ terms is precisely what we have on the left-hand side of the inductive hypothesis. Hence, by writing

$1+2+3+\cdots+(k+1) = 1+2+\cdots+k+(k+1),$

we can regroup the right-hand side as

$1+2+3+\cdots+(k+1) = [1+2+\cdots+k]+(k+1),$

so that $$1+2+\cdots+k$$ can be replaced by $$\frac{k(k+1)}{2}$$, according to the inductive hypothesis. With additional algebraic manipulation, we try to show that the sum does equal to $$\frac{(k+1)(k+2)}{2}$$.

We proceed by induction on $$n$$. When $$n=1$$, the left-hand side of the identity reduces to 1, and the right-hand side becomes $$\frac{1\cdot2}{2}=1$$; hence, the identity holds when $$n=1$$. Assume it holds when $$n=k$$ for some integer $$k\geq1$$; that is, assume that

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

for some integer $$k\geq1$$. We want to show that it also holds when $$n=k+1$$. In other words, we want to show that

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

Using the inductive hypothesis, we find

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

Therefore, the identity also holds when $$n=k+1$$. This completes the induction.

We can use the summation notation (also called the sigma notation) to abbreviate a sum. For example, the sum in the last example can be written as

$\sum_{i=1}^n i.$

The letter $$i$$ is the index of summation. By putting $$i=1$$ under $$\sum$$ and $$n$$ above, we declare that the sum starts with $$i=1$$, and ranges through $$i=2$$, $$i=3$$, and so on, until $$i=n$$. The quantity that follows $$\sum$$ describes the pattern of the terms that we are adding in the summation. Accordingly,

$\sum_{i=1}^{10} i^2 = 1^2+2^2+3^2+\cdots+10^2.$

In general, the sum of the first $$n$$ terms in a sequence $$\{a_1,a_2,a_3,\ldots\,\}$$ is denoted $$\sum_{i=1}^n a_i$$. Observe that

$\sum_{i=1}^{k+1} a_i = \left(\sum_{i=1}^k a_i\right) + a_{k+1},$

which provides the link between $$P(k+1)$$ and $$P(k)$$ in an induction proof.

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

Use mathematical induction to show that, for all integers $$n\geq1$$, $\sum_{i=1}^n i^2 = 1^2+2^2+3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}.$

We proceed by induction on $$n$$. When $$n=1$$, the left-hand side reduces to $$1^2=1$$, and the right-hand side becomes $$\frac{1\cdot2\cdot3}{6}=1$$; hence, the identity holds when $$n=1$$. Assume it holds when $$n=k$$ for some integer $$k\geq1$$; that is, assume that $\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$ for some integer $$k\geq1$$. We want to show that it still holds when $$n=k+1$$. In other words, we want to show that $\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)[2(k+1)+1]}{6} = \frac{(k+1)(k+2)(2k+3)}{6}.$ From the inductive hypothesis, we find \begin{aligned} \sum_{i=1}^{k+1} i^2 &=& \left(\sum_{i=1}^k i^2\right) + (k+1)^2 \\ &=& \frac{k(k+1)(2k+1)}{6}+(k+1)^2 \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)[k(2k+1)+6(k+1)] \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)(2k^2+7k+6) \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)(k+2)(2k+3). \end{aligned} Therefore, the identity also holds when $$n=k+1$$. This completes the induction.

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

Use mathematical induction to show that $3+\sum_{i=1}^n (3+5i) = \frac{(n+1)(5n+6)}{2}$ for all integers $$n\geq1$$.

Proceed by induction on $$n$$. When $$n=1$$, the left-hand side reduces to $$3+(3+5)=11$$, and the right-hand side becomes $$\frac{2\cdot11}{2} =11$$; hence, the identity holds when $$n=1$$. Assume it holds when $$n=k$$ for some integer $$k\geq1$$; that is, assume that $3+\sum_{i=1}^k (3+5i) = \frac{(k+1)(5k+6)}{2}$ for some integer $$k\geq1$$. We want to show that it still holds when $$n=k+1$$. In other words, we want to show that $3+\sum_{i=1}^{k+1} (3+5i) = \frac{[(k+1)+1]\,[5(k+1)+6]}{2} = \frac{(k+2)(5k+11)}{2}.$ From the inductive hypothesis, we find \begin{aligned} 3+\sum_{i=1}^{k+1} (3+5i) &=& \left(3+\sum_{i=1}^k (3+5i)\right) + [3+5(k+1)] \\ &=& \frac{(k+1)(5k+6)}{2} + 5k+8 \\ [3pt] &=& \textstyle\frac{1}{2}\,[(k+1)(5k+6)+2(5k+8)] \\ [3pt] &=& \textstyle\frac{1}{2}\,(5k^2+21k+22) \\ [3pt] &=& \textstyle\frac{1}{2}\,(k+2)(5k+11). \end{aligned} This completes the induction.

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

It is time for you to write your own induction proof. Prove that $1\cdot2 + 2\cdot3 + 3\cdot4 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}$ for all integers $$n\geq1$$.

Remark

We give you a hand on this one, after which, you will be on your own. We lay out the template, all you need to do is fill in the blanks.

for some integer $$k\geq1$$. We want to show that it also holds when $$n=k+1$$; that is, we want to show that

It follows from the inductive hypothesis that \begin{aligned} \hskip2in &=& \hskip2in + \hskip1in \\ [6pt] \hskip2in &=& \hskip1in + \hskip1in \\ [6pt] \hskip2in &=& \hskip1in . \end{aligned} This completes the induction.

exercise $$\PageIndex{2}\label{he:induct1-02}$$

Use induction to prove that, for all positive integers $$n$$, $1\cdot2\cdot3 + 2\cdot3\cdot4 + \cdots + n(n+1)(n+2) = \frac{n(n+1)(n+2)(n+3)}{4}.$

exercise $$\PageIndex{3}\label{he:sumfourn}$$

Use induction to prove that, for all positive integers $$n$$, $1+4+4^2+\cdots+4^n = \frac{1}{3}\,(4^{n+1}-1).$

All three steps in an induction proof must be completed; otherwise, the proof may not be correct.

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

Never attempt to prove $$P(k)\Rightarrow P(k+1)$$ by examples alone. Consider $P(n): \qquad n^2+n+11 \mbox{ is prime}.$ In the inductive step, we want to prove that $P(k) \Rightarrow P(k+1) \qquad\mbox{ for \emph{any} } k\geq1.$ The following table verifies that it is true for $$1\leq k\leq 8$$: $\begin{array}{|*{10}{c|}} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline n^2+n+11 & 13 & 17 & 23 & 31 & 41 & 53 & 67 & 83 & 101 \\ \hline \end{array}$ Nonetheless, when $$n=10$$, $$n^2+n+11=121$$ is composite. So $$P(9) \nRightarrow P(10)$$. The inductive step breaks down when $$k=9$$.

Example $$\PageIndex{5}\label{eg:induct1-05}$$

The basis step is equally important. Consider proving $P(n): \qquad 3n+2 = 3q \mbox{ for some integer q}$ for all $$n\in\mathbb{N}$$. Assume $$P(k)$$ is true for some integer $$k\geq1$$; that is, assume $$3k+2=3q$$ for some integer $$q$$. Then $3(k+1)+2 = 3k+3+2 = 3+3q = 3(1+q).$ Therefore, $$3(k+1)+2$$ can be written in the same form. This proves that $$P(k+1)$$ is also true. Does it follow that $$P(n)$$ is true for all integers $$n\geq1$$? We know that $$3n+2$$ cannot be written as a multiple of 3. What is the problem?

Solution

The problem is: we need $$P(k)$$ to be true for at least one value of $$k$$ so as to start the sequence of implications $P(1) \Rightarrow P(2), \qquad P(2) \Rightarrow P(3), \qquad P(3) \Rightarrow P(4), \qquad\ldots$ The induction fails because we have not established the basis step. In fact, $$P(1)$$ is false. Since the first domino does not fall, we cannot even start the chain reaction.

## Remark

Thus far, we have learned how to use mathematical induction to prove identities. In general, we can use mathematical induction to prove a statement about $$n$$. This statement can take the form of an identity, an inequality, or simply a verbal statement about $$n$$. We shall learn more about mathematical induction in the next few sections.

# Summary and Review

• Mathematical induction can be used to prove that a statement about $$n$$ is true for all integers $$n\geq1$$.
• We have to complete three steps.
• In the basis step, verify the statement for $$n=1$$.
• In the inductive hypothesis, assume that the statement holds when $$n=k$$ for some integer $$k\geq1$$.
• In the inductive step, use the information gathered from the inductive hypothesis to prove that the statement also holds when $$n=k+1$$.
• Be sure to complete all three steps.
• Pay attention to the wording. At the beginning, follow the template closely. When you feel comfortable with the whole process, you can start venturing out on your own.

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

Use induction to prove that $1^3+2^3+3^3+\cdots+n^3 = \frac{n^2(n+1)^2}{4}$ for all integers $$n\geq1$$.

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

Use induction to prove that the following identity holds for all integers $$n\geq1$$: $1+3+5+\cdots+(2n-1) = n^2.$

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

Use induction to show that $1+\frac{1}{3}+\frac{1}{3^2}+\cdots+\frac{1}{3^n} = \frac{3}{2}\left(1-\frac{1}{3^{n+1}}\right)$ for all positive integers $$n$$.

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

Use induction to establish the following identity for any integer $$n\geq1$$: $1-3+9-\cdots+(-3)^n = \frac{1-(-3)^{n+1}}{4}.$

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

Use induction to show that, for any integer $$n\geq1$$: $\sum_{i=1}^n i\cdot i! = (n+1)!-1.$

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

Use induction to prove the following identity for integers $$n\geq1$$: $\sum_{i=1}^n \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1}.$

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

Evaluate $$\dd\sum_{i=1}^n \frac{1}{i(i+1)}$$ for a few values of $$n$$. What do you think the result should be? Use induction to prove your conjecture.

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

Use induction to prove that $\sum_{i=1}^n (2i-1)^3 = n^2(2n^2-1)$ whenever $$n$$ is a positive integer.

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

Use induction to show that, for any integer $$n\geq1$$: $1^2-2^2+3^2-\cdots+(-1)^{n-1}n^2 = (-1)^{n-1}\,\frac{n(n+1)}{2}.$

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

Use mathematical induction to show that $\sum_{i=1}^n \frac{i+4}{i(i+1)(i+2)} = \frac{n(3n+7)}{2(n+1)(n+2)}$ for all integers $$n\geq1$$.