Number of binary strings not having even-length runs of $0$ or $1$

Question

I was solving this algorithmic problem. This problem boils down to finding the finding the number of binary strings of given length $n$ such that those strings don't have any even-length run of $0$ or $1$. The post says that the answer is twice the $n$th term of the Fibonacci series, where the term numbering starts at $0$.

I have tried myself to arrive at the same solution but without success. Any help/hint is appreciated.

Answer 1

Let $A_n$ be the number of valid strings of length $n$

We have $A_{n+1} = A_n+A_{n-2}+A_{n-4}+\dots$ with initial conditions $A_0=1$, $A_1=2$ and $A_2=2$ seen by that we can form a valid string of length $n+1$ by taking a shorter string and putting an odd number of whatever the other element that was formerly at the end at the end of the string.

Now... consider the expression for $A_{n-1}$ using the above...

$A_{n-1}=A_{n-2}+A_{n-4}+A_{n-6}+\dots$, so going back to the earlier expression, we have $A_{n+1}=A_n+A_{n-2}+A_{n-4}+\dots=A_n+A_{n-1}$. Noting the recurrence matches the Fibonacci recurrence and noting the values of $A_1$ and $A_2$ give the relationship to the Fibonacci sequence.

Answer 2

Let $a_n$ be the number of admissible length-$n$ strings. Note the following:

• For any admissible string of length $n-1$, there is exactly one way to add one bit on the right to make an admissible string of length $n$: the added bit is different from the last bit to avoid making a forbidden length-2 run.
• For any admissible string of length $n-2$, there is exactly one way to add two identical bits on the right to make an admissible string of length $n$: the added bits are the same as the last bit. The case where the added bits are different has already been covered in the length-$n-1$ case.

Thus we have $a_n=a_{n-1}+a_{n-2}$ – the Fibonacci number relation – and initial values $a_1=a_2=2$. It is now clear that $a_n=2F_n$, with $F_n$ the $n$th Fibonacci number where $F_1=F_2=1$.

Answer 3

Using $z$ for ones and $w$ for zeroes we get the generating function

$$f(z, w) = (1+z+z^3+z^5+\cdots) \\ \times \left(\sum_{q\ge 0} (w+w^3+w^5+\cdots)^q (z+z^3+z^5+\cdots)^q\right) \\ \times (1+w+w^3+w^5+\cdots).$$

This simplifies to

$$f(z, w) = \left(1+\frac{z}{1-z^2}\right) \left(\sum_{q\ge 0} w^q \frac{1}{(1-w^2)^q} z^q \frac{1}{(1-z^2)^q}\right) \left(1+\frac{w}{1-w^2}\right) \\ = \left(1+\frac{z}{1-z^2}\right) \frac{1}{1-wz/(1-w^2)/(1-z^2)} \left(1+\frac{w}{1-w^2}\right) \\ = \left(1+z-z^2\right) \frac{1}{(1-w^2)(1-z^2)-wz} \left(1+w-w^2\right).$$

Since we are only interested in the count we may end the distinction between zeroes and ones to obtain

$$g(z) = \frac{(1+z-z^2)^2}{(1-z^2)^2-z^2} = \frac{(1+z-z^2)^2}{1-3z^2+z^4} = \frac{1+z-z^2}{1-z-z^2}.$$

Hence

$$(1-z-z^2) g(z) = 1 + z - z^2.$$

Extracting coefficients we get

$$[z^0] (1-z-z^2) g(z) = [z^0] g(z) = 1.$$

so that $g_0 = 1.$ We also have

$$[z^1] (1-z-z^2) g(z) = g_1-g_0 = 1$$

so that $g_1 = 2.$ Furthermore

$$[z^2] (1-z-z^2) g(z) = g_2-g_1-g_0 = -1$$

so that $g_2 = 2.$ Finally for $n\ge 3$ we find

$$[z^n] (1-z-z^2) g(z) = 0$$

so that $g_n - g_{n-1} - g_{n-2} = 0$ or

$$g_n = g_{n-1} + g_{n-2}.$$

With $g_1 = 2 F_1$ and $g_2 = 2 F_2$ and the induction hypothesis $g_n = 2 F_n$ we get from the recurrence that $g_n = 2 F_{n-1} + 2 F_{n-2} = 2 F_n$ so that indeed $g_n = 2 F_n$ for $n\ge 1$ as claimed.

Remark. We may also observe that

$$g(z) = 1 + 2 \frac{z}{1-z-z^2}$$

where we recognize the Fibonacci number OGF so that we may conclude by inspection.