Proposition 3.12.
For every positive integer \(n\text{,}\) the sum of the first \(n\) positive integers is \(n(n+1)/2\text{,}\) i.e.,
\begin{equation*}
\sum_{i=1}^n i=\frac{n(n+1)}{2}.
\end{equation*}
Section 3.8 Proofs by Induction
No discussion of recursion and induction would be complete without some obligatory examples of proofs using induction. We start with the “Hello World” example.
For our first version of a proof of Proposition 3.12, we clearly identify the open statement \(S_n\) and describe the proof carefully in terms of \(S_n\text{.}\) As you develop more experience with writing proofs by induction, this will become less essential, as you’ll see in the second version of the proof.
Proof.
Let \(n\) be a positive integer, and let \(S_n\) be the open statement
\begin{equation*}
\sum_{i=1}^n i = \frac{n(n+1)}{2}.
\end{equation*}
We will prove that \(S_n\) is true for all positive integers by induction. For the basis step, we must prove that \(S_1\) is true. When \(n=1\text{,}\) the left-hand side of \(S_n\) is just \(1\text{,}\) while the right-hand side evaluates to \(1(1+1)/2=1\text{.}\) Therefore, \(S_1\) is true.
Next we assume that for some positive integer \(k\text{,}\) \(S_k\) is true. That is, we assume
\begin{equation*}
\sum_{i=1}^k i=\frac{k(k+1)}{2}.
\end{equation*}
We now seek to prove that \(S_{k+1}\) is true, and begin by considering the left-hand side of \(S_{k+1}\text{.}\) We notice that
\begin{equation*}
\sum_{i=1}^{k+1}i=\left(\sum_{i=1}^k i\right) +(k+1)=
\frac{k(k+1)}{2}+(k+1),
\end{equation*}
since our inductive hypothesis that \(S_k\) is true gives us the simpler formula for the summation. Now continuing with a bit of algebra, we find
\begin{equation*}
\frac{k(k+1)}{2}+(k+1)=\frac{k^2+3k+2}{2}=\frac{(k+1)(k+2)}{2}.
\end{equation*}
Therefore, \(S_{k+1}\) is true. Since we have shown that \(S_1\) is true and that for every positive integer \(k\text{,}\) if \(S_k\) is true, then \(S_{k+1}\) is true, we conclude that \(S_n\) is true for all positive integers \(n\) by the Principle of Mathematical Induction.
Before looking at a refined version of this proof, let’s take a moment to discuss the key steps in every proof by induction. The first step is the basis step, in which the open statement \(S_1\) is shown to be true. (It’s worth noting that there’s nothing special about \(1\) here. If we want to prove only that \(S_n\) is true for all integers \(n\geq 5\text{,}\) then proving that \(S_5\) is true is our basis step.) When proving the basis step, if \(S_n\) is an equation, we do not just write down \(S_1\) and move on. We need to prove that \(S_1\) is true. Notice how in the proof above, we discussed the left-hand side of \(S_1\) and the right-hand side of \(S_1\) and concluded that they were equal.
After the basis step comes the inductive step, in which we assume that \(S_k\) is true for some positive integer \(k\) and prove that \(S_{k+1}\) is true. When doing this, we call \(S_k\) our inductive hypothesis. In the inductive step, the most common mistake students make is starting with the entirety of \(S_{k+1}\) and manipulating it until they obtain a true statement. This is dangerous, as it is possible to start with something false and through valid algebraic steps, obtain a true statement. Instead, the best option is to work as with the basis step: if \(S_{k+1}\) is an equation or inequality, work on one side until you find a place to apply the inductive hypothesis and then continue until you obtain the other side. If the algebra gets tricky along the way, you can also work with the left-hand side of \(S_{k+1}\) and separately work with the right-hand side of \(S_{k+1}\text{.}\) If you’re able to manipulate both sides to be in the same form, then you have shown they are equal and \(S_{k+1}\) is true.
Now let’s take a look at a more refined proof of Proposition 3.12. From here on, when we give a proof by induction, we’ll use this style. As you’re getting started with induction proofs, you may find it useful to be more explicit about the steps as we did in the first proof above.
Proof.
We first prove the assertion when \(n=1\text{.}\) For this value of \(n\text{,}\) the left-hand side is just \(1\text{,}\) while the right-hand side evaluates to \(1(1+1)/2=1\text{.}\)
Now assume that for some positive integer \(k\text{,}\) the formula holds when \(n=k\text{,}\) i.e., assume that
\begin{equation*}
\sum_{i=1}^k i=\frac{k(k+1)}{2}.
\end{equation*}
Then it follows that
\begin{equation*}
\sum_{i=1}^{k+1}i=\left(\sum_{i=1}^k i\right) +(k+1)=
\frac{k(k+1)}{2}+(k+1)=\frac{k^2+3k+2}{2}=\frac{(k+1)(k+2)}{2}.
\end{equation*}
Thus the formula also holds when \(n=k+1\text{.}\) By the Principle of Mathematical Induction, it holds for all positive integers \(n\text{.}\)
The preceding arguments are 100% correct… but some combinatorial mathematicians would argue that they may actually hide what is really going on. These folks would much prefer a combinatorial proof, as was provided in Section 2.4. Our perspective is that you should prefer to give a combinatorial proof—when you can find one. But if pressed, you should be able to give a formal proof by mathematical induction.
Here’s a second example, also quite a classic. Again, recall that we gave a combinatorial proof in the last chapter. As you read the proof, make sure you can identify the open statement \(S_n\text{,}\) the basis step, and the inductive step.
Proposition 3.13.
For each positive integer \(n\text{,}\) the sum of the first \(n\) odd positive integers is \(n^2\text{,}\) i.e.,
\begin{equation*}
\sum_{i=1}^n (2i-1)= n^2.
\end{equation*}
Proof.
We will prove this by induction. First, note that the formula holds when \(n=1\text{.}\) Now suppose that \(k\) is a positive integer and that the formula holds when \(n=k\text{,}\) i.e., assume
\begin{equation*}
\sum_{i=1}^k (2i-1)= k^2.
\end{equation*}
Then
\begin{equation*}
\sum_{i=1}^{k+1}(2i-1)=\left(\sum_{i=1}^k 2i-1\right)+2k+1=
k^2+(2k+1)=(k+1)^2.
\end{equation*}
Therefore, the proposition follows by the Principle of Mathematical Induction.
Here’s a more general version of the first result in this section, and again we note that we gave a combinatorial proof in Section 2.4.
Proposition 3.14.
Let \(n\) and \(k\) be non-negative integers with \(n\ge k\text{.}\) Then
\begin{equation*}
\sum_{i=k}^n \binom{i}{k}=\binom{n+1}{k+1}.
\end{equation*}
Proof.
Fix a non-negative integer \(k\text{.}\) We then prove the formula by induction on \(n\text{.}\) If \(n=k\text{,}\) note that the left hand side is just \(\binom{k}{k}=1\text{,}\) while the right hand side is \(\binom{k+1}{k+1}\) which is also \(1\text{.}\) Now assume that \(m\) is a non-negative integer, with \(m\ge k\text{,}\) and that the formula holds when \(n=m\text{,}\) i.e., assume that
\begin{equation*}
\sum_{i=k}^m \binom{i}{k}=\binom{m+1}{k+1}.
\end{equation*}
Then
\begin{align*}
\sum_{i=k}^{m+1}\binom{i}{k} \amp = \sum_{i=k}^{m}\binom{i}{k} +\binom{m+1}{k}\\
\amp =\binom{m+1}{k+1}+\binom{m+1}{k}\\
\amp =\binom{m+2}{k+1}.
\end{align*}
Therefore, the proposition follows by the Principle of Mathematical Induction.
Reading Questions Reading Questions
1.
Suppose that \(t(n)\) is a recursive function defined for \(n\geq 1\) such that \(t(1)=1\) and for \(n\geq 2\text{,}\) \(t(n)=2t(n-1)+1\text{.}\) Create a proof that for all \(n\geq 1\text{,}\) \(t(n) = 2^n - 1\text{.}\)
2.
Write a couple of sentences explaining why the making the inductive hypothesis is not the same as assuming what we are trying to prove.
You have attempted of activities on this page.
