Recursive formula for tiling checkerboard The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper right $1\times 1$ square from the $2\times 2$ tile) requires. The $L$-tiles can be rotated any way.
I began by trying to do a mathematical induction proof but I don't know if I am approaching this the right way. Any help would be appreciated.
 A: Draw the $2\times n$, for some reasonable number $n$. We will concentrate on the left end of your picture. 
The two squares at the end could be filled with two $1\times 1$ tiles. The rest can be done in $t(n-1)$ ways. 
There could be one $1\times 1$ tile at the left end, on the top or on the bottom. The remaining square can be filled by an L in $1$ way, and the rest of the $2\times n$ in $t(n-2)$ ways, for a total of $2t(n-2)$.
Or else the there could be an $L$ filling both squares on the left ($2$ ways), with the remaining square filled by a $1\times 1$. That again gives $2t(n-2)$.
Or else we can have an L on the left filling both squares, and an interlocking L. That gives $2t(n-3)$ ways of filling the rest.
The recurrence is therefore 
$$t(n)=t(n-1)+4t(n-2)+2t(n-3).$$
For completeness, one should give initial conditions $t(0)$, $t(1)$, $t(2)$. 
A: Hint: The last column of your board could have two 1 x 1's, or 
a 1 x 1 and one square from an L (of which the other two squares form the second-last column), or two squares from an L; in the last case the second-last
column has the third square from that L and either a 1 x 1 or a square from another L (whose other two squares form the third-last column).
