\problemdata                                                             
        {Fibonnaci-like series formula} % latex-friendly label for the prob.
        {Strong induction} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Quiz 1, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Let $G_0=1$, $G_1=2$, $G_2=4$ and define $G_n = G_{n-1} +2G_{n-2} + G_{n-3}$ for $n \geq 3$. \\

Show by induction that $G_n\leq(2.2)^n$ for all $n \geq 0$.

\solution{
\begin{proof}
(Base Cases)\\
$n=0$: $1 = 2.2^0$\\
$n=1$: $2 < 2.2^1 = 2.2$\\
$n=2$: $4 < 2.2^2 = 4.84$\\
(Inductive Step) \\
Assume $P(n)$ for all $k$ such that $0 \leq k \leq n$.
\begin{eqnarray*}
G_{n+1} &=& G_n +2G_{n-1} + G_{n-2} \\
&\leq& (2.2)^n + 2(2.2)^{n-1} + (2.2)^{n-2}\\
&=& (2.2)^{n-2} [(2.2)^2 + 2(2.2) + 1]\\
&=& (2.2)^{n-2} [(2.2 + 1)^2]\\
&=& (2.2)^{n-2} (3.2)^2\\
&=& (2.2)^{n-2} (10.24)\\
&<& (2.2)^{n-2} (10.648)\\
&=& (2.2)^{n-2} (2.2)^3\\
&=& (2.2)^{n+1}\\
\end{eqnarray*}
\end{proof}

One common error in this proof was not doing the proper base cases.  Students also had problems using the strong inductive assumptions.  Note that points were also deducted for not adequately showing that $(3.2)^2<(2.2)^3$.
}

\end{problem}
                                 