# Recurrence relation for tiling

You need to tile an $$n \times 1$$ hallway with unlimited supply of $$1 \times 1$$ red tiles, $$2 \times 1$$ red tiles, and $$2 \times 1$$ blue tiles. Write down the recurrence relation formula and initial conditions for the number of ways to tile an $$n \times 1$$ hallway for which you are allowed to use all types of tiles.

My approach: Let $$f(n)$$ denote the number of ways to tile an $$n \times 1$$ hallway.

For $$n = 1$$ we have $$f(1) = 1$$, as we can only fill a $$1 \times 1$$ hallway with a $$1 \times 1$$ red tile.

When $$n = 2$$, we can either fill both spaces with $$1 \times 1$$ red tiles, or a $$2 \times 1$$ red tile, or a $$2 \times 1$$ blue tile. This gives $$f(2) = 3$$.

When $$n = 3$$ we can fill all of them with $$1 \times 1$$ red tiles, or with a $$1 \times 1$$ red tile followed by a $$2 \times 1$$ red or blue tile. Taking into account the possible permutations we have $$f(3) = 5$$.

Case 1: Consider an $$n \times 1$$ hallway as a $$(n-1) \times 1$$ hallway preceding a $$1 \times 1$$ space. To fill the $$1 \times 1$$ space, we can only use a $$1 \times 1$$ red tile.

We can also consider an $$n \times 1$$ hallway as a $$(n-2) \times 1$$ hallway preceding a $$2 \times 1$$ space. Then to fill that $$2 \times 1$$ space, we can use two $$1 \times 1$$ red tiles, which gives us Case 2.

Tiling the $$2 \times 1$$ space with a $$2 \times 1$$ blue tile gives us Case 3, and with a $$2 \times 1$$ red tile gives Case 4.

The 4 cases are disjoint, and hence we get $$f(n) = f(n-1) + 3f(n-2)$$.

However, computationally, I realised that the correct formula is $$f(n) = f(n-1) + 2f(n-2)$$, i.e. we consider cases 2 and 4 to be the same (using two $$1 \times 1$$ red tile is the same as using a single $$2 \times 1$$ red tile), why is that?

I ask this because by manually counting, I get $$f(4) = 11$$, and this is taking into consideration that two consecutive $$1 \times 1$$ red tiles is not the same as a single $$2 \times 1$$ red tile, so intuitively, we should still have $$4$$ disjoint cases instead of considering cases $$2$$ and $$4$$ to be the same.

The issue is not that two $$1 \times 1$$ red tiles are treated the same as a $$2 \times 1$$ red tile. The issue is that your method double counts those tilings that end in two $$1 \times 1$$ red tiles. For example, if you are creating a tiling of length 5, one possibility is to use 5 $$1 \times 1$$ red tiles. Your method counts this by extending 4 $$1 \times 1$$ tiles by a single $$1 \times 1$$ tile, and by extending 3 $$1 \times 1$$ tiles by a pair of $$1 \times 1$$ tiles. In a nutshell, your cases 1 and 2 are not disjoint.