Find a generating function involving a tiling problem 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?
 A: 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}.$$
A: 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))$.
