Skip to main content
Suppose one is presented with the following sequence of equations:
\begin{align*}
1 &=1 \\
1 + 3 &=4 \\
1 + 3 + 5 &=9 \\
1 + 3 + 5 + 7 &=16 \\
1 + 3 + 5 + 7 + 9 &=25
\end{align*}
It is clear that there is a pattern. The numbers on the right side of the equations are the squares $1^{2}$, $2^{2}$, $3^{2}$, $4^{2}$, and $5^{2}$ and, in the equation with $n^{2}$ on the right side, the left side is the sum of the first $n$ odd numbers. The odd numbers are
\begin{align*}
1 &= 2 \cdot 1 -1 \\
3 &= 2 \cdot 2 -1 \\
5 &= 2 \cdot 3 -1 \\
7 &= 2 \cdot 4 -1 \\
9 &= 2 \cdot 5 -1
\end{align*}
and from this it is clear that the $n$th odd number is $2n - 1$. Hence, at least for $n = 1$, $2$, $3$, $4$, or $5$, the following is true:
\begin{equation}\label{eq:induction}
1 + 3 + \cdots + (2n-1) = n^2 \tag{$S_n$}
\end{equation}
The question arises whether the statement \ref{eq:induction} is true for \textit{every} $n$.
There is no hope of separately verifying all these statements because
there are infinitely many of them. A more subtle approach is required.
The idea is as follows: Suppose it is verified that the statement $S_{n+1}$ will be true whenever $S_{n}$ is true. That is, suppose we prove that, \textit{if} $S_{n}$ is true, then it necessarily follows that $S_{n+1}$ is also true. Then, if we can show that $S_{1}$ is true, it follows that $S_{2}$ is true, and from this that $S_{3}$ is true, hence that $S_{4}$
is true, and so on and on. This is the principle of induction. To
express it more compactly, it is useful to have a short way to express
the assertion ``If $S_{n}$ is true, then $S_{n+1}$ is true.'' As in Appendix \ref{chap:appbproofs}, we write this assertion as
\begin{equation*}
S_n \Rightarrow S_{n+1}
\end{equation*}
and read it as `` $S_{n}$ implies $S_{n+1}$.'' We can now state the principle of mathematical induction.
\newpage
\begin{theorem*}{The Principle of Mathematical Induction}{034881}
Suppose $S_{n}$ is a statement about the natural number $n$ for each $n = 1, 2, 3, \dots$.\index{induction!mathematical induction}\index{mathematical induction}
Suppose further that:
\begin{enumerate}
\item $S_{1}$ is true.
\item $S_{n} \Rightarrow S_{n+1}$ for every $n \geq 1$.
\end{enumerate}
Then $S_{n}$ is true for every $n \geq 1$.
\end{theorem*}
\noindent This is one of the most useful
techniques in all of mathematics. It applies in a wide variety of
situations, as the following examples illustrate.
\begin{example}{}{034897}
Show that $1 + 2 + \dots + n = \frac{1}{2}n(n + 1)$ for $n \geq 1$.
\begin{solution}
Let $S_{n}$ be the statement: $1 + 2 + \dots + n = \frac{1}{2}n(n + 1)$ for $n \geq 1$. We apply induction.
\begin{enumerate}
\item $S_{1}$ is true. The statement $S_{1}$ is $1 = \frac{1}{2}1(1 + 1)$, which is true.
\item $S_{n} \Rightarrow S_{n+1}$. We \textit{assume} that $S_{n}$ is true for some $n \geq 1$---that is, that
\begin{equation*}
1+ 2 + \cdots + n = \frac{1}{2} n(n+1)
\end{equation*}
\end{enumerate}
We must prove that the statement
\begin{equation*}
S_{n+1} : 1 + 2 + \cdots + (n+1) = \frac{1}{2} (n+1)(n+2)
\end{equation*}
is also true, and we are entitled to use $S_{n}$ to do so. Now the left side of $S_{n+1}$ is the sum of the first $n + 1$ positive integers. Hence the second-to-last term is $n$, so we can write
\begin{align*}
1 + 2 + \cdots + (n+1) & = (1 + 2+ \cdots + n)+(n+1) \\
&= \frac{1}{2} n(n+1) + (n+1) \quad \mbox{using } S_n \\
& = \frac{1}{2}(n+1)(n+2)
\end{align*}
This shows that $S_{n+1}$ is true and so completes the induction.
\end{solution}
\end{example}
In the verification that $S_{n} \Rightarrow S_{n+1}$, we \textit{assume} that $S_{n}$ is true and use it to deduce that $S_{n+1}$ is true. The assumption that $S_{n}$ is true is sometimes called the \textbf{induction hypothesis}\index{induction hypothesis}.
\begin{example}{}{034928}
If $x$ is any number such that $x \neq 1$, show that $1 + x + x^2 + \cdots + x^n = \frac{x^{n+1}-1}{x-1}$ for $n \geq 1$.
\begin{solution}
Let $S_{n}$ be the statement: $1 + x + x^2 + \cdots + x^n = \frac{x^{n+1}-1}{x-1}$.
\begin{enumerate}
\item $S_{1}$ is true. $S_{1}$ reads $ 1+x = \frac{x^2 -1}{x-1}$, which is true because $x^{2} - 1 = (x - 1)(x + 1)$.
\item $S_{n} \Rightarrow S_{n+1}$. Assume the truth of $S_{n}$ : $1 + x + x^{2} + \dots + x^n = \frac{x^{n+1}-1}{x-1}$.
\end{enumerate}
We must \textit{deduce} from this the truth of $S_{n+1}$: $1 + x + x^{2} + \cdot + x^{n+1} = \frac{x^{n+2}-1}{x-1}$. Starting with the left side of $S_{n+1}$ and using the induction hypothesis, we find
\begin{align*}
1 +x + x^2 + \cdots + x^{n+1} & = (1 + x + x^2 + \cdots + x^n) + x^{n+1} \\
&= \frac{x^{n+1} -1 }{x-1} + x^{n+1} \\
&= \frac{x^{n+1} -1 + x^{n+1}(x-1)}{x-1} \\
&= \frac{x^{n+2}-1}{x-1}
\end{align*}
This shows that $S_{n+1}$ is true and so completes the induction.
\end{solution}
\end{example}
Both of these examples involve formulas for a certain sum, and it is often convenient to use summation notation. For example, $ \sum_{k=1}^{n} (2k-1)$ means that in the expression $(2k - 1)$, $k$ is to be given the values $k = 1, k = 2, k = 3, \dots , k = n$, and then the resulting $n$ numbers are to be added. The same thing applies to other expressions involving $k$. For example,
\begin{align*}
\sum_{k=1}^{n} k^3 &=1^3 + 2^3 + \cdots + n^3 \\
\sum_{k=1}^{5} (3k-1) &= (3 \cdot 1 -1) + (3 \cdot 2 - 1) + (3 \cdot 3 - 1) +(3 \cdot 4 - 1) + (3 \cdot 5 - 1)
\end{align*}
The next example involves this notation.
\begin{example}{}{034966}
Show that $\sum_{k=1}^{n} (3k^2-k) = n^2(n+1)$ for each $n \geq 1$.
\begin{solution}
Let $S_{n}$ be the statement: $\sum_{k=1}^{n} (3k^2-k) = n^2(n+1)$.
\begin{enumerate}
\item $S_{1}$ is true. $S_{1}$ reads $(3 \cdot 1^2 - 1) = 1^{2}(1 + 1)$, which is true.
\item $S_{n} \Rightarrow S_{n+1}$. Assume that $S_{n}$ is true. We must prove $S_{n+1}$:
\begin{align*}
\sum_{k=1}^{n+1} (3k^2-k) &= \sum_{k=1}^{n}(3k^2-k) + [3(n+1)^2 - (n+1)] \\
& = n^2(n+1)+(n+1)[3(n+1)-1] \tag{using $S_n$} \\
& = (n+1)[n^2 + 3n+2]\\
& = (n+1)[(n+1)(n+2)] \\
& = (n+1)^2(n+2)
\end{align*}
\end{enumerate}
This proves that $S_{n+1}$ is true.
\end{solution}
\end{example}
\noindent We now turn to examples wherein induction is used to prove propositions that do not involve sums.
\begin{example}{}{034992}
Show that $7^n + 2$ is a multiple of $3$ for all $n \geq 1$.
\begin{solution}
\begin{enumerate}
\item $S_{1}$ is true: $7^1 + 2 = 9$ is a multiple of $3$.
\item $S_{n} \Rightarrow S_{n+1}$. Assume that $7^n + 2$ is a multiple of $3$ for some $n \geq 1$; say, $7^n + 2 = 3m$ for some integer $m$. Then
\begin{equation*}
7^{n+1} +2 = 7(7^n) +2 = 7(3m-2)+2 = 21m-12 = 3(7m-4)
\end{equation*}
so $7^{n+1} + 2$ is also a multiple of $3$. This proves that $S_{n+1}$ is true.
\end{enumerate}
\end{solution}
\end{example}
In all the foregoing examples, we have used the principle of induction starting at $1$; that is, we have verified that $S_{1}$ is true and that $S_{n} \Rightarrow S_{n+1}$ for each $n \geq 1$, and then we have concluded that $S_{n}$ is true for every $n \geq 1$. But there is nothing special about $1$ here. If $m$ is some fixed integer and we verify that
\begin{enumerate}
\item $S_{m}$ is true.
\item $S_{n} \Rightarrow S_{n+1}$ for every $n \geq m$.
\end{enumerate}
\noindent then it follows that $S_{n}$ is true for every $n \geq m$.
This ``extended'' induction principle is just as plausible as the
induction principle and can, in fact, be proved by induction. The next
example will illustrate it. Recall that if $n$ is a positive integer, the number $n!$ (which is read ``$n$-factorial'') is the product
\begin{equation*}
n! = n(n-1)(n-2)\cdots 3 \cdot 2 \cdot 1
\end{equation*}
of all the numbers from $n$ to $1$. Thus $2! = 2$, $3! = 6$, and so on.
\begin{example}{}{035027}
Show that $2^n < n!$ for all $n \geq 4$.
\begin{solution}
Observe that $2^n < n!$ is actually false if $n = 1, 2, 3$.
\begin{enumerate}
\item $S_{4}$ is true. $2^4 = 16 < 24 = 4!$.
\item $S_{n} \Rightarrow S_{n+1}$ if $n \geq 4$. Assume that $S_{n}$ is true; that is, $2^n < n!$. Then
\begin{equation*}
\begin{array}{rcll}
2^{n+1} & = &2 \cdot 2^n &\\
& < &2 \cdot n! & \mbox{because } 2^n < n! \\
& < &(n+1)n! & \mbox{because } 2<n+1\\>< 2^{n}$
\end{ex}
\begin{ex}
For any integer $m > 0$, $m!n! < (m + n)!$
\end{ex}
\begin{ex}
$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}} \leq 2\sqrt{n}-1$
\begin{sol}
$2\sqrt{n} - 1 + \frac{1}{\sqrt{n+1}} = \frac{2\sqrt{n^2+n}+1}{\sqrt{n+1}} - 1 < \frac{2(n+1)}{\sqrt{n+1}}-1 = 2\sqrt{n+1}-1$
\end{sol}
\end{ex}
\begin{ex}
$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}} \geq \sqrt{n}$
\end{ex}
\begin{ex}
$n^{3} + (n + 1)^{3} + (n + 2)^{3}$ is a multiple of $9$.
\end{ex}
\begin{ex}
$5n + 3$ is a multiple of $4$.
\end{ex}
\begin{ex}
$n^{3} - n$ is a multiple of $3$.
\begin{sol}
If $n^{3} -n = 3k$, then $(n + 1)^{3} - (n + 1) = 3k + 3n^{2} + 3n = 3(k + n^{2} + n)$
\end{sol}
\end{ex}
\begin{ex}
$3^{2n+1} + 2^{n+2}$ is a multiple of $7$.
\end{ex}
\begin{ex}
Let $B_{n} = 1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \dots + n \cdot n$! Find a formula for $B_{n}$ and prove it.
\begin{sol}
$B_{n} = (n + 1)! - 1$
\end{sol}
\end{ex}
\begin{ex}
Let
\begin{equation*}
A_n = (1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{4})\cdots (1-\frac{1}{n})
\end{equation*}
Find a formula for $A_n$ and prove it.
\end{ex}
\begin{ex}
Suppose $S_{n}$ is a statement about $n$ for each $n \geq 1$. Explain what must be done to prove that $S_{n}$ is true for all $n \geq 1$ if it is known that:
\begin{enumerate}[label={\alph*.}]
\item $S_{n} \Rightarrow S_{n+2}$ for each $n \geq 1$.
\item $S_{n} \Rightarrow S_{n+8}$ for each $n \geq 1$.
\item $S_{n} \Rightarrow S_{n+1}$ for each $n \geq 10$.
\item Both $S_{n}$ and $S_{n+1} \Rightarrow S_{n+2}$ for each $n \geq 1$.
\end{enumerate}
\begin{sol}
\begin{enumerate}[label={\alph*.}]
\setcounter{enumi}{1}
\item Verify each of $S_{1}, S_{2}, \dots, S_{8}$.
\end{enumerate}
\end{sol}
\end{ex}
\begin{ex}
If $S_{n}$ is a statement for each $n \geq 1$, argue that $S_{n}$ is true for all $n \geq 1$ if it is known that the following two conditions hold:
\begin{enumerate}
\item $S_{n} \Rightarrow S_{n-1}$ for each $n \geq 2$.
\item $S_{n}$ is true for infinitely many values of $n$.
\end{enumerate}
\end{ex}
\begin{ex}
Suppose a sequence $a_{1}, a_{2}, \dots$ of numbers is given that satisfies:
\begin{enumerate}
\item $a_{1} = 2$.
\item $a_{n+1} = 2a_{n}$ for each $n \geq 1$.
Formulate a theorem giving $a_{n}$ in terms of $n$, and prove your result by induction.
\end{enumerate}
\end{ex}
\begin{ex}
Suppose a sequence $a_{1}, a_{2}, \dots$ of numbers is given that satisfies:
\begin{enumerate}
\item $a_{1} = b$.
\item $a_{n+1} = ca_{n} + b$ for $n = 1, 2, 3, \dots$.
Formulate a theorem giving $a_{n}$ in terms of $n$, and prove your result by induction.
\end{enumerate}
\end{ex}
\begin{ex}
\begin{enumerate}[label={\alph*.}]
\item Show that $n^{2} \leq 2^{n}$ for all $n \geq 4$.
\item Show that $n^{3} \leq 2^{n}$ for all $n \geq 10$.
\end{enumerate}
\end{ex}
\end{multicols}
