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.