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.

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.
