Section 4.2 Mathematical Induction
In this section we learn a new proof technique, mathematical induction. This technique is useful for proving statements about the positive (or nonnegative) integers. It is based on the following principle.
Principle of Mathematical Induction.
Let \(P(n)\) be a property defined for integers \(n\text{,}\) and let \(a\) be a fixed integer. Suppose the following are true:
\(P(a)\) is true;
For all \(k\in\mathbb{Z}\) with \(k\geq a\text{,}\) if \(P(k)\) is true then \(P(k+1)\) is true;
then for all \(n\geq a\text{,}\) \(P(n)\) is true.
The way to think about the Principle of Mathematical Induction is that if you know the statement is true for some starting value, (\(P(a)\) is true), and if you can show that knowing the statement is true for some value allows you to know it is true for the next value (\(P(k)\rightarrow P(k+1)\)), then you know it for all values greater than or equal to \(a\text{.}\)
So why should this work? Suppose you know two things:
\(P(1)\) is true, and
\(P(k)\rightarrow P(k+1)\text{.}\)
Note, you do not know \(P(k)\) is true, just that if it is true, then \(P(k+1)\) will be true. Now since \(P(1)\) is true, by (2), \(P(2)\) must be true. Since \(P(2)\) is true, \(P(3)\) must be true, etc. In this way we can see that \(P(n)\) must be true for all \(n\geq 1\text{.}\)
The Principle of Mathematical Induction lets us skip all the intermediate steps, \(P(1)\rightarrow P(2), P(2)\rightarrow P(3),\) and conclude \(P(n)\) once we have (1) and (2).
Structure of a Mathematical Induction Proof.
To prove \(P(n), \forall n\geq 1\text{,}\)
Conclude \(P(n)\) is true for all \(n\geq 1\)
In the above structure we used \(a=1\) for simplicity, but an induction proof could have a base step starting at a different \(a\text{.}\) Most commonly, the base step starts with 0 or 1.
When writing induction proofs, make sure you use the actual statement you are proving rather than the notation \(P(1), P(k), P(n)\text{.}\)
Activity 4.2.1. Adding the Next Term.
Since the induction step in mathematical induction connects a statement about \(k\) to a statement about \(k+1\text{,}\) we need to be comfortable with the relationship between sums of \(k\) terms and sums of \(k+1\) terms.
(a)
Write out the summation for \(\sum_{i=1}^{k}i\text{.}\)
(b)
Write out the summation for \(\sum_{i=1}^{k+1}i\text{.}\)
(c)
How do (a) and (b) differ?
Example 4.2.1. Proof by Induction: Summation Formula.
Prove \(\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\) for \(n\geq 1\text{.}\)
Proof.
Base Step: Let \(n=1\text{.}\) Then
\begin{gather*}
\sum_{i=1}^{n}i=\sum_{i=1}^{1}i=1\\
\frac{n(n+1)}{2}=\frac{1(1+1)}{2}=1
\end{gather*}
Since the left hand side of the equation equals the right hand side, \(\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\) for \(n=1\text{.}\)
Induction Step:
Assume \(\sum_{i=1}^{k}i=\frac{k(k+1)}{2}\) for some \(k\geq 1\text{.}\)
Show \(\sum_{i=1}^{k+1}i=\frac{(k+1)(k+2)}{2}\text{.}\)
Proof of induction step:
\begin{align*}
\sum_{i=1}^{k}i&=\frac{k(k+1)}{2}\ \ \textrm{ by the induction assumption}\\
\sum_{i=1}^{k+1}i&= \sum_{i=1}^{k}i+(k+1)\ \ \textrm{ add the } k+1 \textrm{ term of the sum}\\
&=\frac{k(k+1)}{2}+(k+1)\\
&=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}\\
&=\frac{k(k+1)+2(k+1)}{2}\ \ \textrm{ factor out }(k+1) \textrm{ on the top}\\
&=\frac{(k+1)(k+2)}{2}.
\end{align*}
Thus, \(\sum_{i=1}^{k+1}i=\frac{(k+1)(k+2)}{2}\text{.}\)
Hence, by induction \(\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\) for \(n\geq 1\text{.}\)
Note, in the base step we looked at each side of what we wanted to show separately. We can refer to this as a “left hand side/ right hand side proof”, or in short hand, a LHS/RHS proof. If we just start with the equation we want to show, then we are assuming what we are trying to prove. To avoid this, it is best, when trying to show two things are equal in the base step, to do a LHS/ RHS proof.
Example 4.2.1 now gives us a useful formula for finding the sum of 1 through
\(n\text{:}\)
\begin{equation}
\sum_{i=1}^{n}i=\frac{n(n+1)}{2}.\tag{4.2.1}
\end{equation}
Activity 4.2.2. Adding \(k+1\) Terms.
Before the next example, we practice the relationship between sums of \(k\) terms and sums of \(k+1\) terms.
(a)
Write out the summation for \(\sum_{i=0}^{k}r^i\text{.}\)
(b)
Write out the summation for \(\sum_{i=0}^{k+1}r^i\text{.}\)
(c)
How do (a) and (b) differ?
Example 4.2.2. Proof by Induction: Powers of 2.
Prove \(\sum_{i=0}^{n}2^i=2^{n+1}-1\) for \(n\geq 0\text{.}\)
Proof.
Base Step: Let \(n=0\text{.}\) Then
\begin{gather*}
\sum_{i=0}^{0}2^i=2^0=1\\
2^{0+1}-1=2-1=1
\end{gather*}
Since the left hand side of the equation equals the right hand side, \(\sum_{i=0}^{n}2^i=2^{n+1}-1\) for \(n=0\text{.}\)
Induction Step:
Assume \(\sum_{i=0}^{k}2^i=2^{k+1}-1\) for some \(k\geq 0\text{.}\)
Show \(\sum_{i=0}^{k+1}2^i=2^{k+2}-1\text{.}\)
Proof of induction step:
\begin{align*}
\sum_{i=0}^{k}2^i&=2^{k+1}-1 \textrm{ by the induction assumption}\\
\sum_{i=0}^{k+1}2^i&= \sum_{i=0}^{k}2^i+(2^{k+1}) \textrm{ add the } k+1 \textrm{ term of the sum}\\
&=2^{k+1}-1+2^{k+1}\\
&=2^{k+1}+2^{k+1}-1 \\
&=2^{k+1}(1+1)-1 \\
&=2^{k+1}(2)-1 \\
&=2^{k+2}-1.
\end{align*}
Thus, \(\sum_{i=0}^{k+1}2^i=2^{k+2}-1\text{.}\)
Hence, by induction \(\sum_{i=0}^{n}2^i=2^{n+1}-1\) for \(n\geq 0\text{.}\)
Example 4.2.2 can be generalized to the sum
\(\sum_{i=0}^{n}r^i\text{.}\)
Example 4.2.3. Proof by Induction: Geometric Sum.
Prove \(\sum_{i=0}^{n}r^i=\frac{r^{n+1}-1}{r-1}\) for \(n\geq 0\text{.}\)
Proof.
Base Step: Let \(n=0\text{.}\) Then
\begin{gather*}
\sum_{i=0}^{0}r^i=r^0=1\\
\frac{r^{0+1}-1}{r-1}=\frac{r-1}{r-1}=1
\end{gather*}
Since the left hand side of the equation equals the right hand side, \(\sum_{i=0}^{n}r^i=\frac{r^{n+1}-1}{r-1}\) for \(n=0\text{.}\)
Induction Step:
Assume \(\sum_{i=0}^{k}r^i=\frac{r^{k+1}-1}{r-1}\) for some \(k\geq 0\text{.}\)
Show \(\sum_{i=0}^{k+1}r^i=\frac{r^{k+2}-1}{r-1}\text{.}\)
Proof of induction step:
\begin{align*}
\sum_{i=0}^{k}r^i&=\frac{r^{k+1}-1}{r-1} \textrm{ by the induction assumption}\\
\sum_{i=0}^{k+1}r^i&= \sum_{i=0}^{k}r^i+(r^{k+1}) \textrm{ add the } k+1 \textrm{ term of the sum}\\
&=\frac{r^{k+1}-1}{r-1}+(r^{k+1})\\
&=\frac{r^{k+1}-1}{r-1}+\frac{(r-1)(r^{k+1})}{r-1}\\
&=\frac{r^{k+1}-1+(r-1)(r^{k+1})}{r-1} \textrm{ factor out } r^{k+1} \textrm{ on the top}\\
&=\frac{r^{k+1}(1+r-1)-1}{r-1} \\
&=\frac{r^{k+1}(r)-1}{r-1} \\
&=\frac{r^{k+2}-1}{r-1}.
\end{align*}
Thus, \(\sum_{i=0}^{k+1}r^i=\frac{r^{k+2}-1}{r-1}\text{.}\)
Hence, by induction \(\sum_{i=0}^{n}r^i=\frac{r^{n+1}-1}{r-1}\) for \(n\geq 0\text{.}\)
The sum in
Example 4.2.3 is called a
geometric sum. Now we have a useful formula for the sum of
\(r^i\) for various values of
\(r>1\text{:}\)
\begin{equation}
\sum_{i=0}^{n}r^i=\frac{r^{n+1}-1}{r-1}.\tag{4.2.2}
\end{equation}
Activity 4.2.3. Practice with Induction.
Suppose you want to prove \(\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}\) for all \(n\geq 1\) by induction.
(a)
What would you want to prove in the base step?
(b)
What should you assume in the induction step?
(c)
What should you show in the induction step?
(d)
Now try to put this all together in the form of an induction proof. If you are unable to prove it, where do you get stuck?
The
closed form of a sum is the computational formula for the sum. For example, the closed form of
\(\sum_{i=0}^{n}2^i\) is
\(2^{n+1}-1\text{,}\) as proved in
Example 4.2.2.
Exercises Exercises
1.
Use mathematical induction to prove for all integers \(n\geq 1\text{,}\)
\begin{equation*}
\sum_{i=1}^n 2i=n^2+n.
\end{equation*}
2.
Use mathematical induction to prove for all integers \(n\geq 1\text{,}\)
\begin{equation*}
\sum_{i=1}^ni^3=\Bigl[\frac{n(n+1)}{2}\Bigr]^2.
\end{equation*}
3.
Use mathematical induction to prove for all integers \(n\geq 1\text{,}\)
\begin{equation*}
\sum_{i=1}^{n}i(i!)=(n+1)!-1.
\end{equation*}
4.
Use
Example 4.2.3 to find a formula for
\(\sum_{i=0}^n 3^i\text{.}\) Prove your formula directly using induction.
5.
Find a formula for \(\sum_{i=0}^n 2i-1\text{.}\) Prove your formula using induction.
6.
Observe that
\begin{align*}
\frac{1}{1\cdot 3}\amp =\frac{1}{3}\\
\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}\amp =\frac{2}{5}\\
\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}+\frac{1}{5\cdot 7}\amp =\frac{3}{7}\\
\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}+\frac{1}{5\cdot 7}+\frac{1}{7\cdot 9}\amp =\frac{4}{9}
\end{align*}
Conjecture a general formula for \(\sum_{i=1}^{n}\frac{1}{(2i-1)(2i+1)}\text{,}\) and prove your conjecture by mathematical induction.
7.
Evaluate the sum \(\sum_{i=1}^{n}\frac{i}{(i+1)!}\) for all \(n=1, 2, 3, 4, 5\text{.}\) Make a conjecture for a formula for the sum for a general \(n\text{,}\) and prove your conjecture by induction.
