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) 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:

I considered , 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?