Find the number of ways an 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's supposed to be solved using a generating function or recurrence since it was in a chapter of generating functions.
I had some ideas:
(i) \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:
\sum a_{n}x^{^{n}}=(1+x^2+x^4+...)(1+x+x^2)
I considered 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?