# find the recurrence relation (homework)

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!

• Hint: Count separately the stacks of n napkins ending with a green napkin and those ending with a non-green napkin. What does that give you? – Did Apr 28 '14 at 5:49

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