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

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

• Usually, in problems like this, you would try a few cases (say for $n$ from $1$ to $4$ or $6$ or something), and see if you can spot some pattern. Next, you would use that pattern to come up with a guess at a formula. Then comes the induction part of the proof, showing that the formula you have is indeed correct. You should at least try the cases yourself before coming here. – Arthur Dec 13 '14 at 19:15
• i guess the formula is this : T(k) = T(k-1) + T(k-2) + 1 . the parentheses are indices – ms95 Dec 13 '14 at 19:17
• Good. Together with $T(1)=1$ and $T(2)=3$, does that formula work for $k=3$ or $4$? – Arthur Dec 13 '14 at 19:21
• i guess it does – ms95 Dec 13 '14 at 19:22
• ok thanks i did the rest . thank you so much – ms95 Dec 13 '14 at 20:02

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.

• The recursion is $T_n = T_{n-1} + 2T_{n-2}$ and $T_1= 1$ and $T_2=3$.
• The closed form is $$\frac{2^{n+1} - (-1)^{n+1}}{3}.$$
• Should be $T_n=T_{n-1}+2T_{n-2}$. – paw88789 Dec 13 '14 at 20:50