Find a recurrence relation for the number of ways to make a stack of green, yellow, and orange napkins so no two green napkins are next to each other.

Question

I'm new to recurrence relations and I'm having trouble figuring out this problem:

Find a recurrence relation for the number of ways to make a stack of green, yellow, and orange napkins so that no two green napkins are next to each other.

Right now I've come up with $$a_n=2a_{n-1}+2a_{n-2}$$ but I'm not sure if this is right.

Any help would be great!

Answer 1

Consider a stack of $n$ napkins. If it ends in non-green, any stack of $n - 1$ came before; if it ends in green, the next to last is non-green, and before those last two there is a stack of $n - 2$. See how many choices you have in each case. Make sure to add initial conditions (numer of stacks with 0 napkins and with 1).