Exercise 4

A $2\times n$ checkerboard is to be tiled using two types of tiles. The first tile is a $1\times 1$ square tile. The second tile is called an $L$-tile and is formed by removing the upper-right $1\times 1$ square from a $2\times 2$ tile. The $L$-tiles can be used in any of the four ways they can be rotated. (That is, the “missing square” can be in any of four positions.) Let $t(n)$ denote the number of tilings of the $2\times n$ checkerboard using $1\times 1$ tiles and $L$-tiles. Find a recursive formula for $t(n)$ and use it to determine $t(7)$.