\problem 
[Shafi -- from spring96]
Mary received $n$ dollars for her birthday and will spend some of the
money each week until it is all used up.  Each week, Mary will either buy
a box of chocolates (costing one dollar), go to a movie (two dollars), or
go to a concert (also two dollars).  Let $M_n$ be the number of weekly
histories of how Mary can spend her money.  For example, there are exactly
five different weekly histories for a three dollar expenditure:
(chocolates, concert), (concert, chocolates), (chocolates, movie), (movie,
chocolates), and (chocolates, chocolates, chocolates).

\bparts
\ppart Exhibit a degree two, linear, homogeneous recurrence satisfied
by $M_{n}$.

{\bf Answer}:
%\begin{proof}
\[
M_n = M_{n-1} + 2M_{n-2}
\]
%\end{proof}

\ppart Describe appropriate initial conditions and find a closed-form
solution for $M_n$.

{\bf Answer}:

Initial conditions: $M_1 = 1$, $M_2 = 3$.

Closed form solution: 
\[ M_n = (2/3)2^n + (1/3)(-1)^n \]

\eparts
