Carrot the cat likes taking naps in one of four locations: the rug, the bed, the ledge, and the sink. Carrot has the following conditions:
• He will not sleep in the sink twice in a row
• He will sleep on the ledge only if he slept on the rug the previous time
Let L(n) be the number of possible sequences of locations for n naps, where n ≥0.
(a) Give a recurrence relation for L(n).
(b) Give the initial conditions for your recurrence. Include only the minimum necessary conditions.