1 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.

a (5 points) Write a recurrence for C(n) in terms of C(n − 1) and C(n − 2).

Soln. C(n) = −C(n − 1) + 2 ∗ C(n − 2)

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?

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