# Need to find the recurrence equation for coloring a 1 by n chessboard

So the question asks me to find the number of ways H[n] to color a 1 by n chessboard with 3 colors - red, blue and white such that the number of red squares is even and number of blue squares is at least one. I am doing it in this way -

1.If the first square is white then the remaining n-1 squares can be colored in H[n-1] ways.

2.If the first square is red then another red will be needed in the n-1 remaining squares and the rest n-2 can be colored in H[n-2] ways. (i.e (n-1)*H[n-2])

3.And now is the problem with blue. If I put blue in the first square and say that the rest n-1 squares can be colored in H[n-1] ways that will be wrong as I already have a blue and may not need any more(while H[n-1] requires one blue at least). I thought of adding H'[n-1] to H[n] = H[n-1] + (n-1)*H[n-2] which gives H[n] = H[n-1] + (n-1)*H[n-2] + H'[n-1] where H'[n] is the number of ways to fill n squares with no blue squares(so H'[n] = (n-1)*H'[n-2] + H'[n-1]). So now I'm kind of really confused how to solve such an equation ->

H[n] = H[n-1] + (n-1)*H[n-2] + H'[n-1]. (I am specifically asked not to use exponential generating function to solve problem).

-
Not much of a "chessboard" if it's $1 \times n$, and three colours as well. –  Robert Israel Jul 23 '12 at 7:23
Yea i know, the book I'm using refers to these boards as x by n chessboards a lot of times. –  Andariel Jul 23 '12 at 7:26
Your (2) overcounts: for $n=5$ it counts RRRRB three times, once for each of the last three red squares. –  Brian M. Scott Jul 23 '12 at 7:27
@BrianM.Scott Can you tell me the right expression for (2)? –  Andariel Jul 23 '12 at 7:35

I wouldn’t actually use a recurrence to solve this problem. Let $c_n$ be the number of ways of coloring the $1\times n$ board with an even number of red cells, and let $b_n$ be the number of these that have no blue cells. Then $h_n=c_n-b_n$, where $h_n$ is the number of colorings with an even number of red cells and at least one blue cell, $$c_n=\sum_k\binom{n}{2k}2^{n-2k}\;,$$ and $$b_n=\sum_k\binom{n}{2k}\;.$$

Then

\begin{align*} c_{n+1}&=\sum_k\binom{n+1}{2k}2^{n+1-2k}\\ &=\sum_k\left(\binom{n}{2k}+\binom{n}{2k-1}\right)2^{n+1-2k}\\ &=2c_n+\sum_k\binom{n}{2k-1}2^{n-(2k-1)}\\ &=2c_n+\sum_k\binom{n}k2^{n-k}-\sum_k\binom{n}{2k}2^{n-2k}\\ &=2c_n+\sum_k\binom{n}k1^k2^{n-k}-c_n\\ &=c_n+3^n \end{align*}

Clearly $c_0=1$, so

$$c_n=1+\sum_{k=0}^{n-1}3^k\;,$$

which is easy to evaluate in closed form. And $b_n$ is just the number of subsets of $\{1,\dots,n\}$ of even cardinality, so it’s also easy to evaluate in closed form.

However, if you want a recurrence, you can probably get one without too much trouble by working backwards from this solution.

-
Thanks a lot for this solution. I agree this problem is really more suited for calculating without resorting to recurrences.(can't upvote anyone as I need more reputation, but anyways, thanks) . –  Andariel Jul 23 '12 at 8:11
Hint: Let $X(n)$ be the number of ways without requiring at least one blue square, and $Y(n)$ the number of ways with no blue squares. Then $H(n) = X(n) - Y(n)$.
This problem can be found in Principle and Techniques in Combinatorics Exercise 5 #31. The only difference is that each square is colored by a color... We use the exponential generating function to solve this problem...For a color red (since the number of square is even) we have $\frac{e^x+e^{-x}}2$ and for the other color we have $e^{2x}$. Thus, we have $\frac{e^{3x}+e^x}2$ which give us (1/2)\sum ({3x}^n/n!+{x^n}/n!). Hence, a_n=(1/2)(3^n+1).