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!

  • 1
    $\begingroup$ 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? $\endgroup$ – 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.