\problemdata                                                             
        {Linear Recurrence} % latex-friendly label for the prob.
        {Linear Recurrences} % The topic(s) of the problem content.  
        {Fall 97} % Source (if known)                                          
        {S01 Quiz 2, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
For each of the following recurrences, find a closed-form solution
for $T(n)$.
\begin{problemparts}

\problempart

$$
T(n+1) = 8T(n) - 16T(n-1)
$$

with the initial conditions $T(0) = 1, T(1) =12$. {\bf (5 points)}
%\vspace*{3.5in}

\solution{
  The characteristic polynomial $x^2-8x+16 = (x-4)^2$ has a
  double root at~$4$; thus the solution has the form $T(n) = a4^n + bn4^n$.
  Plugging in the initial conditions gives the linear equations
  $1 = T(0) = a$ and $12 = T(1) = 4a + 4b = 4 + 4b$. Thus, the solution is
  $T(n) = (1 + 2n)4^n$.}

\problempart

$$
T(n+1) = 8T(n) - 16T(n-1) + 2^n
$$

with the initial conditions $T(0) = \frac52, T(1) = 5$. {\bf (5 points)}

\solution{
  A particular solution is of the form $k2^n$.
  Plugging in the equation we obtain $k=\frac12$.
  We proved in the first part of the problem that the homogeneous
  solution is $a4^n + bn4^n$.

  So the general solution has the form
  $a4^n + bn4^n + 2^{n-1}$
  We use the initial conditions to solve for $a,b$ to obtain
  $a = 2$, $b = -1$

  So the answer is $T(n) = (2-n)4^n+2^{n-1}.$

  Common errors on this part of the problem included reusing constants from part a or solving for them without including the particular solution in.  This error cost a couple of points.  Another common error was shifting all the n's but not shifting the n term on $2^n$.  This also cost two points.  Any arithmetic mistakes cost a point.  
}
\end{problemparts}
\end{problem}
                                 