Recursion- to pave 2xn rectangle 
Can you explain the recursion for the number of ways to pave rectangle of size $2\times n$ with tiles of size: $1\times 1$, $1\times 2$, $2\times 1$. When $a_n$ is the possible ways to pave rectangle of size $2\times n$ and $b_n$ is number of ways to pave $2\times n$ rectangles with missing square at the corner.
$$a_{n+2}=2a_{n+1}+a_n+2b_{n+1}$$
and also
$$b_{n+1}=a_n+b_n$$
How are those expression created?
Why is it $2a_{n+1}+a_n$ and not $2a_{n}+a_{n+1}$?
 A: Consider a $2 \times (n+2)$ rectangle tiled in this way, and consider in particular the way the first column is tiled.


*

*If the first column is tiled with a vertical $2 \times 1$ tile, there are $a_{n+1}$ ways to tile the remaining grid.

*If the first column is tiled with two $1 \times 1$ tiles, there are $a_{n+1}$ ways to tile the remaining grid.

*If the first column is tiled with a $1 \times 1$ tile and half of a $2 \times 1$ tile, first there are $2$ ways to do this ($1 \times 1$ on top and $2 \times 1$ on bottom, or vice versa), and second, there are $b_{n+1}$ ways to tile the remaining grid.  In total there are $2b_{n+1}$ ways to tile in this case.

*Otherwise, the first column is tiled with two horizontal halves of $2 \times 1$ tiles.  In this case, the first two columns are taken up, and there are $a_{n}$ ways to tile the remaining grid.
In total, this shows that
$$
a_{n+2} = a_{n+1} + a_{n+1} + 2b_{n+1} + a_n
$$
I'll let you prove $b_{n+1} = a_n + b_n$ yourself.  Hint: consider the slot below the missing corner, and how it could be tiled.
