Find a recurrence relation for the number of ways to arrange $n$ dominoes to fill a $2$ by $n$ checkerboard.

I am having trouble with this question, please take a look at it:

Find a recurrence relation for the number of ways to arrange $n$ dominoes to fill a $2$ by $n$ checkerboard.

I have just started reading the topic and it is one of the starting problem. Please help. You can give me some hints, a complete answer is also appreciated.

Thanks

On the rightmost end of your board you can have either one vertical domino, or two horizontal dominoes on top of one another. That means that whatever your current arrangement, it's an $n-2$-arrangement with two horizontal dominoes stuck to the end, or an $n-1$-arrangement with one vertical domino stuck to the end. There is clearly no overlap between these two cases (whichever piece fills the rightmost bottom square can't both be vertical and horizontal), and they cover all possibilities (said piece has to be either vertical or horizontal). Thus the recurrence relation is $$ a_n = a_{n-1} + a_{n-2} $$ or, in other words, the Fibonacci recurrence. It also so happens that $a_0 = a_1 = 1$, so you really do get the Fibonacci sequence from this.

I assume that your dominos are $2 \times 1$ rectangles, which can be arranged horizontally or vertically inside your $2 \times n$ "frame".

The idea is to look at the "last" domino/s.

More precisely: Let $p_n$ the number of ways to arrange your $n$ dominos. If you consider an arbitrary arrangement (of this $p_n$-many) there are only two possibilities:

First: The last domino stands "vertically".

Second: The last two dominos stand "horizontally".

Can you finish?