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

Hint 3

Let's look at the ones with red on top. If there is a red chip on top, then the next chip underneath must be white or blue, and any n-1 high stack with white or blue on top will work, so we know that

r(n) = w(n-1) + b(n-1).

Now work out formulas for the other colors. Finally think about how to use these formulas to get a formula for a(n).

The Rest of the Solution

The formulas for red, white, and blue are

r(n) = w(n-1) + b(n-1)
w(n) = r(n-1) + b(n-1)
b(n) = r(n-1) + w(n-1) + b(n-1)

Note that blue is special, because there are no restrictions on stacks with blue on top. To get back to a formula for a(n) the obvious step is to add together these three formulas:

a(n) = r(n) + w(n) + b(n) = 2r(n-1) + 2w(n-1) + 3b(n-1) = 2a(n-1) + b(n-1)

Now we note that b(n) = r(n-1) + w(n-1) + b(n-1) = a(n-1) and therefore b(n-1) = a(n-2) which gives us the final formula

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

More is Less

It often happens when you want to derive some result that there is a generalization or a stronger result that is easier to get. Pólya calls this the Inventor's Paradox: "The more ambitious plan may have more chances of success." In this problem we attacked the apparently more difficult problem of counting each kind of stack according to the top chip. Some other examples of the Inventor's Paradox:

The sum of the first n cubes is a square.
[Prove it is the particular square (n(n+1)/2)².]
If m is an integer, and a is an integer relatively prime to m, then a has a multiplicative inverse modulo m (that is, there is an x such that ax=1 mod m).
[Prove that ax takes on all values relatively prime to m as a varies over all values relatively prime to m; in particular it takes the value 1.]
(Fermat's Last Theorem for exponent 4) Show that there are no positive integers x, y, z such that x⁴ + y⁴ = z⁴.
[Prove there are no solutions to x⁴ + y⁴ = z².]

References

George Pólya, How To Solve It, Princeton University Press, 1957. The Inventor's Paradox is discussed on pp. 121-122, and the sum of the first n cubes is an example on pp. 115 ff.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1979. The multiplicative inverse is proved on pp. 51-52, and Fermat's Last Theorem for exponent 4 is proved on pp. 191-192.
Click here to view the original problem submitted by Thermos.