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)
 A: 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.$$
A: If you’d rather avoid Twiceler’s approach of using several recurrences to keep track of subcases and solving them simultaneously, you can. The trade-off is that Twiceler’s approach makes it easier to get started but a bit more work to finish.
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}$.
