In how many ways can a $ 2 \times n $ rectangle be tiled by $ 2 \times 1 $ or $ 1 \times 1 $ tiles?

Question

This problem is from the book "Problem Solving Strategies" by Arthur Engel (Chapter 9, problem 64) and the solution given there is $\ a_0 = 1, \ a_1 = 2,\ a_2 = 7$ and the recurrence relation being $\ a_n = 3a_{n-1} + \ a_{n-2}\ - \ a_{n-3}$
I'd like to know how did we get this recurrence.

Answer 1

We can define $A(n)$ as the number of ways to tile a $2 \times n$ rectangle, $B(n)$ as the number of ways to tile a $2 \times n$ rectangle plus one square and $C(n)$ as the number of ways to tile a $2 \times n$ rectangle plus one horizontal domino. We can set up a set of coupled recurrences by imagining we add one piece that covers the leftmost uncovered square or the top one if there are two. $$A(n)=A(n-1)+B(n-1)+C(n-2)\\B(n)=A(n)+B(n-1)+C(n-1)\\C(n)=A(n)$$ Because we can get a $2 \times n$ rectangle by adding a vertical domino to a $2 \times n-1$ rectangle or filling in the hole on the other shapes, we can get a $B$ shape by adding $1 \times 1$ to a rectangle, by adding a $1 \times 2$ to a B shape or by adding a $1 \times 1$ to a C shape, and we can only get a C shape by adding a horizontal $1 \times 2$ to a rectangle. Then we get $$A(n)=A(n-1)+B(n-1)+A(n-2)\\ B(n)=A(n)+B(n-1)+A(n-1)\\ B(n-1)-B(n-2)=A(n-1)+A(n-2)\\ A(n-1)=A(n-2)+B(n-2)+A(n-3)\\ A(n)-A(n-1)=A(n-1)+B(n-1)-B(n-2)-A(n-3)\\ A(n)=3A(n-1)+A(n-2)-A(n-3)$$

The sequence is given in OEIS A030186 and begins $$1, 2, 7, 22, 71, 228, 733, 2356, 7573, 24342, 78243, 251498, 808395, 2598440, 8352217, 26846696, 86293865, 277376074, 891575391, 2865808382, 9211624463, 29609106380, 95173135221, 305916887580, 983314691581, 3160687827102 $$
The fourth comment says this is the count of the tilings we want.