Finding the reccurence relation from a problem. let $f(n)$ be the number if ways to lay down tiles in a formation of size 2 x n
using tiles of size: $$
        \begin{matrix}
        1  \\
        1  \\
        \end{matrix}
$$
and tiles of size: $$
        \begin{matrix}
        1 & 1 & 1 \\
        1 & \\
        \end{matrix}
$$
Turning and reflecting the tiles is legal.
So what i thought was that theres 2 illegal starts:
$$
        \begin{matrix}
        1 & 1 & 1 \\
         &  & 1 \\
        \end{matrix}
$$
and :   \begin{matrix}
         &  & 1 \\
        1 & 1 & 1 \\
        \end{matrix}
And so there's the options to set the 2X1 tile vertically and the $f_{n-1}$
and all the rest of the cases (6 more) i set the first two so it fills the formation legally and then $f_{n-2}$,
So suming up all:
$f_n=f_{n-1}+6f_{n-2}$
$f_0=0 , f_1=1$
but it is not working... help would be appreciated. thanks.
 A: There are $8$ different ways the left most tiles of a $2\times n$ tiling could look.


*

*It could have a vertical $2\times 1$ tile. This only takes up 1 horizontal slot. This gives us a summand of $f_{n-1}$ in the reccurence.

*It could have $2$ horizontal $2\times 1$ tiles. This formation takes up 2 horizontal slots. This gives us a summand of $f_{n-2}$.

*It could start with an L shaped tile and a horizontal $2\times 1$ tile in 4 different ways (crudely pictured below). All of these take up $3$ horizontal slots. This gives us a summand of $4f_{n-3}$.


*

*$$\begin{matrix} a & a & b \\ b& b & b\end{matrix}$$

*$$\begin{matrix} b & a & a \\ b& b & b\end{matrix}$$

*$$\begin{matrix} b & b & b \\ a& a & b\end{matrix}$$

*$$\begin{matrix} b & b & b \\ b& a & a\end{matrix}$$


*It could start with 2 interlocking L shaped tiles in 2 different ways. These formations take up $4$ horizontal slots. This gives us a summand of $2f_{n-4}$.


*

*$$\begin{matrix} a & a & a & b \\ a & b & b & b\end{matrix}$$

*$$\begin{matrix} b & a & a & a \\ b & b & b & a\end{matrix}$$



So the total recurrence relation is given by $f_n=f_{n-1}+f_{n-2}+4f_{n-3}+2f_{n-4}$ with starting conditions $f_0 = 1$, $f_1=1$, $f_2=2$ and $f_3=7$.
Note that $f_0 =1$ and not $0$ since there is exactly one way to tile a $2\times 0$ strip, it uses $0$ tiles.
