Let $h_n$ denote the number of ways that a 1×n rectangle can be tiled with red, blue, green, and yellow squares, where there must be an even number of red tiles, an even number of blue tiles, and at least two green tiles. Find a formula for $h_n$.
Work so far: My approach is to find a recursive formula for $h_n$ in terms of $h_{n-1}$ and maybe $h_{n-2}$ and then use generating functions to solve for $h_n$. I can't figure out how to do this because, for instance, we know a tiling of length two has to be (green, green), but then the since the order matters there are 3 places to put a yellow to get a tiling of length 3, but only 1 green (and no blue or red for that matter). So, if we ignore the red and blue, the number of choices to turn a length $n-1$ tiling into a length $n$ tiling is dependent on $n-1-g$ and $n-1-y$, where $g$ is the number of green tiles and $y$ is the number of yellow. I thought to take the average of all the possible $g$s and $y$s for this, but stopped because I have no idea how to apply the same reasoning to the red and blue.
The other thing I noticed was that exactly half of the possible tilings have an even number red tiles, likewise for blue.
Thanks in advance.
First of all, for the condition "at least two green tiles", it is much easier to count the complementary class of sequences with either zero or one green tile. To this end, let $a_n$ be the number of sequences of length $n$, where each entry is either red, blue, or yellow (no green), with an even number of red and blue. Then the answer to the complementary question is $$ \text{# R,B,Y,G sequences with even R, even B, $<2$ G}=\underbrace{a_n}_\text{zero green tiles}+\underbrace{na_{n-1}}_\text{one green tile} $$ All that remains is, how to compute $a_n$?
You said you noticed that exactly half of the tilings have an even number of reds. This is not exactly correct, but it is almost correct, and the idea leads to a solution. I will use the strategy that I used in a previous answer, where the problem was to count sequences of three possible symbols where one symbol is required to appear an even number of times, and another is required to appear an odd number of times.
Let us divide the set of $3^n$ tilings into pairs, as follows. Given a tiling, find the leftmost tile which is either red or yellow, and replace it with the other color, yellow or red, to get the tiling it is paired with. The only exception is the tiling with all blues, which is not paired with anything.
In each pair of tilings, exactly one of the tilings has an even number of reds. In addition, the all-blue tiling has an even number of reds. It follows that the number of even-red tilings is $$ \text{# of R,B,Y sequences with even R }=\frac{3^n-1}{2}+1=\frac{3^n+1}2 $$
Now, of these $(3^n+1)/2$ sequences with an even number of reds, we need to count the number with an even number of blues. Again, we use a pairing strategy. Find the leftmost instance of blue or yellow, and change it to yellow or blue, respectively. The only potentially unpaired sequence is the sequence of all reds; there is one such sequence when $n$ is even, and zero such sequences when $n$ is odd. Therefore, using similar logic to before, we conclude that $$ a_n=\text{# of R,B,Y sequences with even R and even B}= \begin{cases} \frac12\left(\frac{3^n+1}{2}-1\right)+1 & \text{if $n$ is even} \\ \frac12\left(\frac{3^n+1}{2}\right) & \text{if $n$ is odd} \end{cases} $$
Both of these pairing/matching methods are often referred to as sign reversing involutions.