\documentstyle{article}

\setlength{\textwidth6.5in}
\setlength{\textheight8.8in}
\setlength{\oddsidemargin0in}
\setlength{\topmargin-0.3in}
\setlength{\unitlength}{1cm}

\begin{document}
\section{Recurrences: 10 points}

Consider a certain species of cannabilistic lichen. Let there also be
anti-lichen. The amazing interaction between lichen and
anti-lichen is that, if $n$ lichen are eaten and only $k$ lichen exist,
and $n > k$, the result is $n-k$ anti-lichen! Similarly, if $n$
anti-lichen are eaten and only $k$ anti-lichen exist,
and $n > k$, the result is $n-k$ lichen. However, an anti-lichen and a
lichen annihilate each other in a blinding flash of licht (sic) whenever
they simultaneously exist.

On every day $n$, each lichen which is at least one day old eats two lichen, and
each anti-lichen which is at least one day old eats two anti-lichen,
while each lichen which existed two days before causes two new lichen to
come into being
(through spores), and
each anti-lichen which existed two days before causes two new
anti-lichen to come into being (through anti-spores). 

Interestingly, we can model $x$ anti-lichen as ($-x$) lichen. So from now
on we only talk about the number of lichen, $C(n)$, but we allow $C(n)$
to dip below 0.

\begin{enumerate}
\item[a] (5 points)
Write a recurrence for $C(n)$ in terms of $C(n-1)$ and $C(n-2)$.

{\bf Soln.} $C(n) = -C(n-1) + 2*C(n-2)$

\item[b] (5 points)
If there 10 lichen on day 0 and 1 lichen on day 1, \\
C(0) = 10, C(1) = 1,\\
how many lichen are
there on day $n$?

{\bf Soln.} Solving our linear homogeneous recurrence yields\\
$r^2 = -r + 2$ which is $r^2 + r - 2 = 0$ so $r = \{-2,1\}$\\
$C(n) = a*(-2)^n + b*(1)^n$\\
plugging in our boundary conditions yields the system\\
10 = a+b, 1 = -2a+b\\
which gives back\\
a = 3, b = 7\\
for a final solution\\
$C(n) = 3*(-2)^n + 7$

\end{enumerate}


\end{document}
