Bit strings of length $n$ in which any two consecutive $1$'s are separated by an even number of $0$’s

Question

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.

Answer 1

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).

Answer 2

Here's another approach. Use the graph as in my previous answer, but don't bother with the starting state $S$, we can start at $A$ (we start with no zeros and then can have a zero or a one so it's OK). The graph looks like this:

Let's define $a_n, b_n, c_n, d_n, e_n$ to be the number of walks on the graph that start from $A$ and after $n$ steps end up in $A, B, C, D, E$. What we want to calculate is the total number of approved strings:

$$x_n = a_n+b_n+c_n+d_n.$$

We notice these facts:

• $a_n = 1$
• $b_n = b_{n-2}+b_{n-3}$, and $b_0=0, b_1=b_2 = 1$
• $c_n = c_{n-1}+c_{n-2}-c_{n-4}$, and $c_0=c_1=0, c_2=c_3=1$
• $d_n = c_{n-1}$, and $d_0=0$

The first is obvious, since only the string $00\dots0$ can end up in $A$.
Also, the last since we can only arrive to $D$ from $C$.

Let's prove the other two inductively on $n$. First notice a helpful equation from the fact that we can arrive to $C$ from $B$ or from $D$:

• $\pmb{c_{m}} = b_{m-1} + d_{m-1} = \pmb{b_{m}+b_{m-1}-1}$, since $b_{m} = d_{m-1}+1$ (remember $a_m = 1$)

Let's now do the induction step for $b_{n+1}$:

$$b_{n+1} = a_{n}+ d_{n} = 1 + c_{n-1} = b_{n-1}+b_{n-2}$$

Then for $c_{n+1}$. I found it easier to start with what we want, that is:

$$c_n+c_{n-1}-c_{n-3} \\ = b_n+b_{n-1}-1 + b_{n-1}+b_{n-2}-1 - (b_{n-3}+b_{n-4}-1)\\ = b_n+b_{n-1}-1 + b_{n-1}+b_{n-2}-1 - b_{n-1} +1 \\ = b_n-1+ b_{n-1}+b_{n-2}\\ = b_n-1+ b_{n+1}\\ = c_{n+1}. $$

The base cases can be checked easily (for example with the matrix approach), here are how the sequences begin

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1...
0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28...
0, 0, 1, 1, 2, 3, 4, 6, 8, 11, 15, 20, 27, 36, 48...
0, 0, 0, 1, 1, 2, 3, 4, 6, 8, 11, 15, 20, 27, 36...

Then finally we also find a recursion for the sum of these, it is actually the same recurrence as for $c$ and $d$

$$x_n = x_{n-1}+x_{n-2}-x_{n-4} \text{ and } x_0=1, x_1=2, x_3=3$$

Let's prove this with induction and also here it's easier to start with the right hand side. The $c$ and $d$ terms gather nicely, $a$ is just the $1$ that survives and noticing that $b_{n}-b_{n-3}=b_{n-2}$ and then that $b_{n-2}+b_{n-3}=b_{n}$ proves the result.