\problemdata     
{S01-PS6-6}           
{Recurrences}              
{S99-PS7, S01-PS6} 		
{S01 Karger}



\begin{problem}


Suppose that the catch of lobsters each year is
the average of the catch for the last two years.  The catch in year 0
was 1000 pounds and the catch in year 1 was 2500 pounds.

\begin{problemparts}
\problempart

 Express the catch of lobsters in year $n$ using
a recurrence relation and sufficient base cases.

\solution{
\begin{eqnarray*}
L_0 & = & 1000 \\
L_1 & = & 2500 \\
L_n & = & \frac{L_{n-1} + L_{n-2}}{2} \quad \quad (n \geq 2)
\end{eqnarray*}
}

\problempart

Solve the recurrence to determine the catch in year $n$.

\solution{The characteristic equation is $2 r^2 - r - 1 = 0$.  This
equation has roots $r = 1$ and $r = - \frac{1}{2}$.  Thus, the
solution has the form

\begin{eqnarray*}
L_n     & = &   A \cdot 1^n + B \cdot \left(- \frac{1}{2} \right)^n.
\end{eqnarray*}

Substituting the base cases gives a system of linear equations:

\begin{eqnarray*}
1000    & = &   A + B \\
2500    & = &   A - \frac{1}{2} B
\end{eqnarray*}

Solving these equations gives $A = 2000$ and $B = -1000$.  Thus the
complete solutions is

\begin{eqnarray*}
L_n & = & 2000 - 1000 \cdot \left(- \frac{1}{2} \right)^n.
\end{eqnarray*}
}

\problempart

 What constant will the annual lobster catch approach in
the distant future?

\solution{
\begin{eqnarray*}
\lim_{n \rightarrow \infty} 2000 - 1000 \cdot \left(- \frac{1}{2} \right)^n
        & = &   2000 \text{ pounds per year}
\end{eqnarray*}
}

\end{problemparts}

\end{problem}
