1
$\begingroup$

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)

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

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.$$

$\endgroup$
  • $\begingroup$ Yes, but how do you solve for the recurrence relation of $h_n$? $\endgroup$ – user67253 Mar 25 '13 at 6:40
3
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy