| Left hand side of equation | Right hand side of equation | |
|---|---|---|
| n = \({\color{Red}0}\) | \(2^0 = 1\) | \(2^{{\color{Red}0}+1}-1 = 1\) |
| n = \({\color{Red}1}\) | \(2^0 + 2^1 = 3\) | \(2^{{\color{Red}1}+1}-1 = 3\) |
| n = \({\color{Red}2}\) | \(2^0 + 2^1 +2^2 = 7\) | \(2^{{\color{Red}2}+1}-1 = 7\) |
| n = \({\color{Red}3}\) | \(2^0 + 2^1 +2^2 + 2^3 = 15\) | \(2^{{\color{Red}3}+1}-1 = 15\) |
| \(\dots\) | \(\dots\) | \(\dots\) |
| \({\color{Red}n}\) | \(2^0 + 2^1 +2^2 + 2^3 + \dots + 2^n\) | \(2^{{\color{Red}n}+1}-1\) |
As shown by the examples above, the equation is true for all values of n ≥ 0, thus the claim is true. ■
This is not a proof by induction. Showing a statement holds for a few values of n does not estabish that the statement is true for all infinitely many values of n.
Base Case (n = 1): We must show that the equation \(\sum_{i=1}^{n}i=\frac{n\cdot(n+1)}{2}\) is true when n=1. When n=1, the left hand side of the equation is a summation consisting of a single term, namely 1. When n=1, the right hand side of the equation is \(\frac{1\cdot(1+1)}{2}\), which equals 1. Since both sides of the equation are equal when n=1, our base case holds.
Inductive Case (n ≥ 2): Let us assume that the equation is true for n, i.e., that \(\sum_{i=1}^{\color{Red}n}i=\frac{{\color{Red}n}\cdot({\color{Red}n}+1)}{2}\) holds (this is our inductive assumption!) and we will prove that the equation is true for n+1, i.e., that \(\sum_{i=1}^{{\color{Red}{n+1}}}i=\frac{({\color{Red}{n+1}})\cdot({\color{Red}{n+1}}+1)}{2}\). Clearly, adding n + 1 to both sides of the equation yields the result that we are trying to prove. ■
The base case is well argued. The inductive case starts off well (stating clearly the inductive assumption) but the final sentence of the inductive case is vague and does not rigorously establish the inductive case. The second equation (involving n + 1) should be established through a series of steps and each step should be justified, e.g., by inductive assumption or by algebra.
Base Case (n = 1): We must show that the inequality \(n\) < \(2^n\) is true when n=1. When n=1, the left hand side of the inequality is 1. When n=1, the right hand side of the inequality is 2^1, which equals 2. Since the left hand side equals 1 and the right hand side equals 2, the left hand side is strictly less than the right hand side and our base case holds.
Inductive Case (n ≥ 2): Let us assume that the inequality is true for n, i.e., that \({\color{Red}n}\) < \(2^{\color{Red}n}\) holds (this is our inductive assumption!) and we will prove that the inequality is true for n+1, i.e., that \({\color{Red}{n+1}}\) < \(2^{\color{Red}{n+1}}\). Here, we will start with the expression \(2^{n+1}\) and, step by step, we will establish that \(2^{n+1}\) is strictly greater than \(n+1\):
\(\begin{array}{rll} 2^{n+1}&= 2 \cdot 2^n & \hspace{20pt}{\color{Blue}{\text{by algebra}}}\\ &> 2 \cdot n & \hspace{20pt}{\color{Blue}{\text{by inductive assumption}}}\\ &= n + n & \hspace{20pt}{\color{Blue}{\text{by algebra}}}\\ &\geq n + 1 & \hspace{20pt}{\color{Blue}{\text{since n ≥ 1}}} \end{array}\)
Thus, \(2^{n+1}\) > \(n+1\), and the inductive case holds. ■
The base case correctly establishes the claim for n = 1. The inductive case does a nice job of justifying each step, using the inductive assumption, and establishing the claim via induction for all infinitely many n ≥ 2. The proof is correct.