Deriving the generating function of a divide and conquer type recurrence relation I am working through Analysis of Algorithms by Sedgewick/Flajolet
On problem 3.44 I am given the recurrence, and I need to come up with a generating function.  I have tried the various methods in the section (it isn't linear, I don't see how to do with a differential equation, nor does it appear to be a composition), but haven't had any success.
$f_{2n}=f_{2n-1}+f_n $ with $n>1$ and $f_0=0$
$f_{2n+1}=f_{2n}$ with $n>0$ and $f_1=1$
Thank you.
 A: If $F_0(z)=\sum f_{2n}z^{2n}$ and $F_1(z)=\sum f_{2n+1}z^{2n+1}$ then I suppose it is easy to get from above equations to find $F_0$ and $F_1$. Then if $F(z)=\sum f_nz^n$ we have $F_0(z)=\frac{F(z)+F(-z)}{2}$, $F_1(z)=\frac{F_0(z)-F(-z)}{2}$, and $F(z)=F_0(z)+F_1(z)$.
We are going to take the equations, multiply by $z^{2n}$ and add for all $n$. We get form the first equation
$$F_0(z)=zF_1(z)+F(z^2)$$
From the second equation we get 
$$F_1(z)=zF_0(z)$$
The equations might get altered by adding certain polynomials depending on the initial conditions and the domain of the recurrences.
A: I think the first equation in the problem statement should be
$f_{2n}=f_{2n-1}+f_n $ with $n \ge 1$ and $f_0=0$.
Otherwise, as noted by RGB, there is no way to find $f_2$.
Let $F(x) = \sum_{n=0}^{\infty}f_{n} x^{n}$.
Note that we have 
$\sum_{n=0}^{\infty}f_{2n} x^{2n}= \sum_{n=0}^{\infty} f_{2n-1} x^{2n} + \sum_{n=0}^{\infty} f_n x^{2n} \qquad$ so
$(1/2) [F(x)-F(-x)] = (1/2) \; x\; [F(x)-F(-x)] +F(x^2)$
$(1-x) F(x) + (1+x) F(-x) = 2 F(x^2) \qquad(*)$
Now starting from the second equation in the problem statement,
$\sum_{n=1}^{\infty} f_{2n+1} x^{2n+1} = \sum_{n=1}^{\infty} f_{2n} x^{2n+1}$ so
$\sum_{n=0}^{\infty} f_{2n+1} x^{2n+1} - x = \sum_{n=0}^{\infty} f_{2n} x^{2n+1}$
$(1/2) [F(x) - F(-x)] - x = (1/2) \; x \; [F(x) + F(-x)]$
$(1-x) F(x) -2x = (1+x) F(-x)$
Substituting into (*), we have
$2 (1-x) \; F(x) -2x = 2 F(x^2) \qquad$ so
$F(x) = \frac{F(x^2)}{1-x} +\frac{x}{1-x}$
Iterating this equation, we find
$F(x) = \frac{F(x^4)}{(1-x)(1-x^2)} +\frac{x}{1-x} + \frac{x^2}{(1-x)(1-x^2)}$
$= \frac{F(x^8)}{(1-x)(1-x^2)(1-x^4)} +\frac{x}{1-x} + \frac{x^2}{(1-x)(1-x^2)} + \frac{x^4}{(1-x)(1-x^2)(1-x^4)}$
which may allow us to guess
$F(x) = \frac{1}{(1-x)(1-x^2)(1-x^4)(1-x^8)\cdots}+\frac{x}{1-x} + \frac{x^2}{(1-x)(1-x^2)} + \frac{x^4}{(1-x)(1-x^2)(1-x^4)} + \dots$ 
which we can see does satisfy $(1-x) F(x) = F(x^2) + x$.  
It would be nice to find a closed form in terms of a finite number of standard functions, but I don't see how to do that.
