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.
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{.}\)
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.).
In the above structure we used \(a=1\) for simplicitiy, 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.
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.
\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*}
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.
\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*}
The closed form of a sum is the computational formula for the sum. For example, the closed form of \(\sum_{i=0}^{n}3^i\) is \(\frac{3^{n+1}-1}{2}\text{.}\)
