Find generating function expressing number of rectangles

Question

I have a 3 x n rectangle. I need to find a generating function expressing the number of little 1 x 3 rectangles inside this bigger one. How can I do this? I have no idea how to even begin.

Answer 1

Hint: $a_{n+3} = a_n+a_{n+2}$.

Expanded: $a_n$ obviously, is the number of tilings of a $3\times n$ rectangle. Now, consider a $3\times (n+3)$ rectangle. In any tiling, the bottom left corner is either tiled by a vertical tile, or a horizontal tile. In the first case, the rest of the is $3 \times (n+2)$ and can be tiled $a_{n+2}$ ways. Otherwise, the cell just above the bottom left has to be tiled by a horizontal tile, and same for the one above it. In which case the rest is a $3 \times n$ rectangle, which can be tiled $a_n$ ways. These cases are obviously mutually exclusive.

The answer seems to be $$\sum_{n=0}^\infty a_n x^n = \dfrac{1}{1-x-x^3}$$.