I am in a combinatorics class, and I am struggling with finding recurrence relations for problems. For example, "Find a recurrence relation for the number of ways to stack n poker chips if each poker chip is red, white, or blue and blue chips may be adjacent, but no red chips are adjacent and no white chips are adjacent." The answer is:

a(n)= 2a(n-1)+a(n-2),

but I don't see how you get that. Is there some sort of general strategy to use that I am missing?

Hint 1

General Strategy: If there is a recursive counting formula, then there is probably a recursive structure to the things being counted; that is, each item is made up recursively of similar smaller items.

Want another hint? Click here.

Click here for the complete solution.