Number of binary strings not having even-length runs of $0$ or $1$ 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.
 A: 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$.
A: 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.

A: 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.
