Let $h_n$ be the number of ways to tile a $1 \times n$ rectangle with $1 \times 1$ tiles that are red or blue and $1 \times 2$ tiles that are green, yellow, or white. Find a closed formula for $$H(x)=\sum_{n\geq0}h_nx^n.$$
I am unsure how to start this problem. Is there a way to solve this without using recurrence relations?
On
In general, if you want the generating function for the number of sequences of objects with a total "weight" of $n$, where each entry is taken independently from a set of $a_1$ objects of weight one, and $a_2$ objects of weight two, etc, then the answer is $$ \frac1{1-(a_1x+a_2x^2+\dots)}=1+\underbrace{(a_1x+a_2x^2+\dots)}_\text{sequences of one object}+\underbrace{(a_1x+a_2x^2+\dots)^2}_\text{sequences of two objects}+\dots $$ In this case, you are counting sequences of tiles, where the weight of a tile is its area, and you want the generating function for tilings of weight $n$. There are two tiles with weight $1$ (two squares), and three tiles of weight $2$, so the answer is $1/(1-(2x+3x^2))$.
A recurrence relation is a good place to start. By considering the possibilities for the first tile, we obtain $$h_n=2h_{n-1}+3h_{n-2}$$ for $n \ge 2$. The boundary conditions are $h_0=1$ and $h_1=2$. Now the recurrence relation and boundary conditions yield $$ H(x)-1-2x = 2 x (H(x)-1) + 3x^2 H(x), $$ from which we find that $$ H(x) = \frac{1}{1-2x-3x^2}. $$ Partial fraction decomposition then yields $$H(x)=\frac{1/4}{1+x}+\frac{3/4}{1-3x},$$ which immediately implies the explicit formula $$h_n=\frac{1}{4}(-1)^n+\frac{3}{4}\cdot 3^n=\frac{(-1)^n+3^{n+1}}{4}.$$