Let $\{b_n\}$ a sequence such that $b_n$ count the number of ways to pave a rectangular floor of dimension $2 \times n$ in using rectangular tiles of dimensions $2 \times 1$ (and $1 \times 2$), square tiles of dimensions $2 \times 2$ and $L-form$ tiles with 3 quares (ask if unclear).
What is the recurrence relation of $b_n$. Justify.
It is very unclear how to get such recurrence relation. How could I get such result?
Hint: Consider the different ways to place blocks to fill the first column. Then consider what the remaining floor looks like. Your recurrence should be based only on the rectangular layout; in the case of the L-shaped tile, you'll need to consider how to place tiles to get the remainder to match this shape.
My approach would be: let $b_n$ be as in the problem; let $c_n$ be the number of ways to cover a $2 \times n$ floor with one square added to the left of the top left square; and $d_n$ be the number of ways to cover a $2 \times n$ floor with one square added to the left of the bottom left square. Then for example, to get $b_n$, at the left edge you can have a square tile; a $1 \times 2$ tile; two $2 \times 1$ tiles; or an L in either one of two ways. Then in each case, considering the number of ways to cover what remains would give you: $$b_n = b_{n-1} + 2 b_{n-2} + c_{n-2} + d_{n-2}, n \ge 2.$$ I'll leave it as an exercise to come up with similar recurrences for $c_n$ and $d_n$.
Now, once you have these, you will need to eliminate $c_n$ and $d_n$ from the recurrence, to get a recurrence involving only $b_n$. Let me know if you have trouble with this step, and I can give some more hints. (One obvious simplification is that $c_n = d_n$ by symmetry.)
You should consider how you can extend an existing $2\times n$ floor tiling.
1) There is only $1$ way to extend it from $n$ to $n+1$.
2) There are $2$ ways to extend it from $n$ to $n+2$, so that the extensions are not decomposable into smaller $2\times m$ rectangles.
3) There are $2$ ways to extend it from $n$ to $n+3$, so that the extensions are not decomposable into smaller $2\times m$ rectangles.
4) There are $2$ ways to extend it from $n$ to $n+4$, so that the extensions are not decomposable into smaller $2\times m$ rectangles.
...
k) There are $2$ ways to extend it from $n$ to $n+k$ ($k\ge5$), so that the extensions are not decomposable into smaller $2\times m$ rectangles.
Then you have the recurrence relation:
$$ b_n=b_{n-1}+ 2\sum_{k=0}^{n-2}b_k, \quad\hbox{(with $b_0=1$)}. $$ We can simplify this relation by subtracting from the above formula the analogous for $b_{n-1}$. We get: $$ b_n-b_{n-1}=b_{n-1}+b_{n-2}, \quad\hbox{that is}:\quad b_n=2b_{n-1}+b_{n-2}. $$ As boundary conditions we can insert here $b_0=b_1=1$.
