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

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.
