## generating function or recurrence problem

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?