\problemdata     
{S01-PS6-5}           
{Recurrences}              
{F98-PS6, S01-PS6} 		
{S01 Karger}


\begin{problem}


Find closed-form solutions to the following
linear recurrences.

\begin{problemparts}
\problempart

 $x_{n} = 5 x_{n-1} - 6 x_{n-2} \quad (x_0 = 0, x_1 = 1)$

\solution{ The characteristic equation is $r^2 - 5 r + 6 = 0$.  The
roots can be found with the quadratic formula:

\begin{eqnarray*}
r_1 & = & 2 \\
r_2 & = & 3
\end{eqnarray*}

This implies a solution of the form

\begin{eqnarray*}
x_n & = & A 2^n + B 3^n.
\end{eqnarray*}

Substituting the initial conditions into this general form gives a
system of linear equations:

\begin{eqnarray*}
0 & = & A + B \\
1 & = & 2 A + 3 B
\end{eqnarray*}

The solution to this system is $A = -1$ and $B = 1$.  Therefore, the
final solution to the recurrence is

\begin{eqnarray*}
x_n & = & 3^n - 2^n.
\end{eqnarray*}
}

\problempart

 $x_{n} = 3x_{n-1} - 2 x_{n-2} + n \quad (x_0 = 0, x_1 = 1)$

\solution{
First, we find the general solution to the homogenous recurrence.  The
characteristic equation is $r^2 - 3r + 2 = 0$.  The roots of this
equation are $r_1 = 1$ and $r_2 = 2$.  Therefore, the general solution
to the homogenous recurrence is

\begin{eqnarray*}
x_n & = & A + B 2^n.
\end{eqnarray*}

Now we must find a particular solution to the recurrence, ignoring the
boundary conditions.  Since the inhomogenous term is linear, we guess
a solution that is quadratic:

\begin{eqnarray*}
an^2+bn+c       & = &   3(a(n-1)^2+b(n-1)+c) - 2(a(n-2)^2+b(n-2)+c) + n \\
                & = &   an^2+2an-5a+bn+b+c+n \\
0               & = &   2an - 5a + b + n
\end{eqnarray*}

This equation is solved by setting $a = -\frac{1}{2}$ and $b =
-\frac{5}{2}$.  Apparently, any value of $c$ gives a valid particular
solution; for simplicity, we choose $c = 0$.  Therefore, the
particular solution is:

\begin{eqnarray*}
x_n     & = &   -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
x_n     & = &   A + B 2^n -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

Substituting the initial conditions gives a system of linear
equations:

\begin{eqnarray*}
0       & = &   A + B \\
1       & = &   A + 2 B - 3
\end{eqnarray*}

The solution to this linear system is $A = -4$ and $B = 4$.
Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
x_n     & = &   2^{n+2} -\frac{1}{2}n^2 - \frac{5}{2} n - 4.
\end{eqnarray*}
}

\end{problemparts}

\end{problem}