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'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) 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?