# Combinatorics tiling squares question

Have a 2xn checkerboard made of 2 kinds of tiles:

• 1x1 square tile
• L-tile, which is a 2x2 square tile with a 1x1 square removed from the corner. This tile can be rotated.

I'm trying to create a recursive formula $t(n)$ to find the number of possible tilings. This is what I have so far:

n=1 t(1) = 1 because can only have 2 1x1 tiles

n=2 t(2) = 5 because you can have:

• All 1x1 tiles (1 option)
• A 1x1 tile and the L-tile rotated 4 different ways (4 options)

n=3 t(3) = 11 because you can have:

• 0 L-tiles, so all 1x1 tiles (1 option)

• 1 L-tile which can be rotated 8 ways and the rest filled with 1x1 squares (8 options)

• 2 L-tiles, which can be rotated 2 ways (2 options)

Is this correct / am I on the right track? I'm not sure how to find the recursive formula this way.

## 1 Answer

That is correct so far for the base cases.

Now, suppose for our induction hypothesis that you know how to count all patterns of length strictly less than $n$ for some $n\geq 4$. We want to figure out how many there are for length $n$.

Consider the last column.

• Case 1: Both spaces are $1\times 1$ tiles

• Case 2: ...

• Case 3: ...

• subcase 3a:
• subcase 3b:

Case 2: One is a $1\times 1$ tile and the other is part of an $L$-shaped tile. Case 3: Both are part of an $L$-shaped tile. Now, consider the second to last column...