Chessboard Combinatorics

Let $h_n$ be the number of different ways to color the squares of an $1$-by-$n$ chessboard using red, white , and blue so that no two adjacent squares are colored white.

(a) Find a recurrence relation that $h_n$ satisfies.

(b) Solve the recurrence relation of $h_n$ obtained in part (a)

• It's 1-by-$n$, so there are no squares which share corners but not edges! – Twiceler Mar 24 '13 at 20:08
• What's a crossboard? Why does it occur in the title but not in the body? – joriki Mar 24 '13 at 20:09
• Sorry my bad typo – user67253 Mar 24 '13 at 20:50

Let $f_n$ be the number of ways to color the squares of a 1-by-$n$ chessboard with a white block at the end. Let $g_n$ be the number of ways to color the squares of a 1-by-$n$ chessboard with a red or blue block at the end. Then $$h_n = f_n + g_n$$ $$f_{n+1} = g_n$$ $$g_{n+1} = 2 h_n.$$
• Yes, but how do you solve for the recurrence relation of $h_n$? – user67253 Mar 25 '13 at 6:40
To build a good coloring of length $n+1$, you can start with any good coloring of length $n$ and add a red or a black square; that gives you $2h_n$ good colorings, and it gives you all of the good colorings that end in a red or a black square, but it doesn’t give you any of the good colorings that end in a white square. However, each of those can be obtained from a good coloring of length $n-1$ by adding either a red and a white square or a black and a white square, and each good coloring of length $n-1$ can be extended in these two ways to a good coloring of length $n+1$ ending in a white square. Thus, $h_{n+1}=2h_n+2h_{n-1}$.