Find the number of ways a_{n}to cover a 2 by n checkerboard with n rectangles (2 by 1 or 1 by 2, also known as dominos).

At least, I think it'ssupposedto be solved using a generating function or recurrence since it was in a chapter of generating functions.

I had some ideas:

(i)$\displaystyle \left \lfloor\frac{n}{2} \right \rfloor=$number of possible 1 by 2 dominos

(ii)the top and bottom row have to be the same configuration

And also some failed attempts, for example:

$\displaystyle \sum a_{n}x^{^{n}}=(1+x^2+x^4+...)(1+x+x^2)$

I considered $\displaystyle n=2l+m$, where l:number of 1 by 2 dominos and m:number of 2 by 1 dominoes, but then I realized I had overlooked the restriction for placing 1 by 2 dominos: the blocks have to be next to each other.

I couldn't find any recurrence relationships.

How should I go about solving this problem?