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.

Hint 2

There really is a recursive structure here, but it's hard to see it, because of the adjacency conditions. Try this: make the problem "harder" by counting stacks separately according to the color of the top chip. So look for formulas involving

r(n), number of n-chip stacks with red on top
w(n), number of n-chip stacks with white on top
b(n), number of n-chip stacks with blue on top

Want another hint? Click here.

Click here for the complete solution.