\problemdata                                                             
        {sum of powers of 2 and 3 formulas} % latex-friendly label for the prob.
        {Induction} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 2, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}        
\begin{problemparts}   
\problempart Prove that $2^0 + 2^1 + \cdots + 2^n = 2^{n+1}-1$, for every $n \in N$.

\solution{
The proof is by induction:\\
Inductive Hypothesis P(n): $2^0 +  2^1 + \cdots + 2^n = 2^{n+1}-1$\\
Base Case: n=0.  $2^0 = 2^{1}-1$. So the base case works.\\
Inductive Step: Assume P(n) in order to show P(n+1) is true.\\
P(n+1) says that $2^0 +  2^1 + \cdots + 2^{n} + 2^{n+1} = 2^{n+2}-1$.\\
From our inductive hypothesis, we know that the first $n+1$ terms of the above e
quation sum up to $2^{n+1}-1$, so let's substitute that in to P(n+1):\\
\begin{eqnarray*}
2^{n+1}-1 + 2^{n+1} & = & 2*(2^{n+1}-1)\\
& = & 2^{n+2}-1\\
\end{eqnarray*}
p(n+1): $2^{n+2}-1 = 2^{n+2}-1$. We have used P(n) to show that P(n+1)
is true, so the proof is complete.
}
\problempart Come up with a formula for $3^0 + 3^1 + \cdots + 3^n$, and prove
your formula.

\solution{
The formula is $\frac{3^{n+1} - 1}{2}$.  The proof by induction is nearly identi
cal to the one above.
}
\end{problemparts}
\end{problem}
                                 
