Let $n \in \mathbb{N}$ and consider a $2\times n$ checkerboard. Let $a_n$ be the number of ways to place $L$-shaped tiles (of size $4$) on the checkerboard. For example, all possible ways for $n=4$ is $a_4=11$. Also, it can be checked that $a_5=19$ . Find a recursive formula for $a_n$ and use it to compute $a_8$.
Here placing no tile counts as one of the possible ways. The size of the tile is fixed.
The recursive formula is of the form $$a_n=Aa_{n−1}+Ba_{n−3}+Ca_{n−4}+Da_{n−5}$$ , $\forall n≥6$,
for some non-zero integers ${A,B,C,D}$.
Best Answer
These are all the possible indecomposable ways to extend a tiling:
We see that $(A,B,C,D)=(1,4,2,2)$ and can work out $a_8=207$. This is A337492 in the OEIS.