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).
 A: 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.
A: 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)$. 
A: 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 (\frac{3x^n}{n!}+\frac{x^n}{n!})$. 
Hence, $a_n=(1/2)(3^n+1)$.
A: Letting $H[n]$ be the number of ways to color the chessboard with an even number of red squares and at least one blue square, and letting $G[n]$ be the very closely related number of ways to color the chessboard with an odd number of red squares with at least one blue square, we notice that $H[n]+G[n]$ is the number of ways to color with at least one blue square, regardless of the condition on red squares.
We get then $H[n] + G[n] = 3^n - 2^n$
We similarly can define $H'[n]$ and $G'[n]$ as the related answers to the counting problem where the conditions on blue squares is removed.
Let us solve the problem with no condition on the blues first.  The first square can either blue white or blue followed by a board with an even number of red squares, or begin with a red square followed by a board with an odd number of red squares.  We further notice that $H'[n]+G'[n]=3^n$.  We have then that $H'[n] = 2H'[n-1] + G'[n-1] = 2H'[n-1]+3^{n-1}-H'[n-1] = H'[n-1]+3^{n-1}$
It follows that when solving along with an initial condition that $H'[1]=2$ that $H'[n]=\frac{1}{2}(3^n+1)$
Back to the original problem, we have then that if the first square is white that the remaining $n-1$ squares must have an even number of red squares and at least one blue.  If the first square is red that the remaining $n-1$ squares must have an odd number of red squares and at least one blue, and finally that if the first square is blue that the remaining squares has an even number of red squares with no further condition on blue squares.
We have then $H[n] = H[n-1] + G[n-1] + H'[n-1]$ and simplifying, $H[n] = H[n-1] + 3^{n-1}-2^{n-1}-H[n-1]+\frac{1}{2}(3^{n-1}+1) = \frac{1}{2}(3^n-2^n+1)$, ironically all of the lower terms having been cancelled and we are already at our closed form solution.
