In this problem, we consider the set of all the binary matrices of size $2\times n$, denoted by $\mathcal B_{2,n}$. Suppose $M\in\mathcal B_{2,n}$ and $P\in \mathcal B_{2,2}$, we define $mch(P,M)$ as the number of occurences of $P$ as blocks in $M$. If $mch(P,M)=0$, we say $M$ avoids $P$.
For example, $P=\begin{pmatrix}0&1\\1&1\end{pmatrix}\in \mathcal B_{2,2}$ and $M=\begin{pmatrix}0&0&1&1&0&1&0&1\\1&1&1&0&1&1&1&0\end{pmatrix}\in \mathcal B_{2,8}$.
We see there are two occurences of $P$: at the second column and fifth column and hence $mch(P,M)=2$.
$a(n)$ is the number of elements in $\mathcal B_{2,n}$ avoiding $P=\begin{pmatrix}0&1\\1&1\end{pmatrix}$.
For example, $a(1)=4$, $a(2)=15$.
Find $a(n)$.