Bit strings of length $n$ in which any two consecutive $1$'s are separated by an even number of $0$’s I want to find the number of bit strings of length $n$ in which any two consecutive $1$'s are separated by an even number of $0$’s
My attempt:
Let $a_n$ be the required number
Take two cases:


*

*The string ends with $1$. In this case, the string must end with $001$. Number of such strings is $a_{n-3}$

*The string ends with $0$. Number of such strings is $a_{n-1}$
Mistake which I found but can't fix in my approach: 
For $n=5$, $10$ is a valid length 2 string, appending $001$ doesn't give a valid length $5$ string.

Form a graph with $6$ nodes: $S, A, B, C, D, E$.


*

*$S$ the starting state (we're here when the string is empty)

*$A$ a state for beginning zeros

*$B$ a state where you have just gotten a one (and the string isn't already rejected)

*$C$ counting zeros after a one, have odd amount

*$D$ counting zeros after a one, have even amount

*$E$ the rejecting state


And the transition matrix, when indexed by this order of states (check each transition and justify them yourself)
$$ P =
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 2 \\
\end{bmatrix}
$$
Now $a_n = 2^n-P^n_{S, E}$. That is, we are looking for the top-right element of $P^n$, it gives the number of walks of length $n$ on the graph that end up in the rejecting state and start from the state $S$.
We can diagonilize $P$ to solve for a formula. Eigenvalues are
$\lambda_1 = 2$
$\lambda_2 \approx 1.32472$
$\lambda_3 = 1$
$\lambda_4 \approx 0.662359 + 0.56228 i$
$\lambda_5 = \bar{\lambda_4}$
$\lambda_6 = 0$
Here $\lambda_2, \lambda_4$ and $\lambda_5$ are the roots of $x^3-x-1$ which we get by dividing the exact roots away from the characteristic polynomial: $\frac{x^6 - 3x^5 + x^4 + 2x^3 + x^2 - 2x}{x(x-1)(x-2)}$.
But then you would need to solve the eigenvectors and the inverse of that matrix and for me it looks pretty messy. Anyway, I think the sequence $a_n$ is this OEIS sequence and there a recurrence is given and from that it is easier to solve for the formula (for example via generating functions).
