Number of ways to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles

Question

How many ways are there to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles? Rotating is allowed.

Progress

Let $T_n$ be the number of ways; then $T_n = T_{ n-1} + T_{ n-2} + 1 $ (based on removing one of tiles, as in quid's answer).

Answer 1

Consider the end (or start) there are three possibilities:

• $2 \times 1$ tile.

• $2 \times 2$ tile.

• two $1 \times 2$ tiles.

Removing these last tiles yields:

• a tiling of $2 \times (n-1)$ grid.

• a tiling of $2 \times (n-2)$ grid.

• a tiling of $2 \times (n-2)$ grid.

From this, and the first values, you get the recursive description that you can solve if you want something more explicit.

---

Added for the record:

• The recursion is $T_n = T_{n-1} + 2T_{n-2}$ and $T_1= 1$ and $T_2=3$.

• This sequence is known as Jacobsthal numbers, except for a shift of the index.

• The closed form is $$\frac{2^{n+1} - (-1)^{n+1}}{3}.$$