Deriving the generating function of a divide and conquer type recurrence relation

Question

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.

Answer 1

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.

Answer 2

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.