Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
How get $f_2$? Can you check for what $n$ can we apply either recurrence? –  ABC Jul 25 '13 at 15:37
    
$f_2=f_{2*1}=f_{1}+f_{1}$ should be found by the first recurrence. –  MathStudent Jul 25 '13 at 16:01
    
OK. The domain $n>1$ confused me. –  ABC Jul 25 '13 at 16:02

2 Answers 2

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.

share|improve this answer
    
Note that the function equation you get is $F_0(z^2)=\dfrac{1-z^2}{1+z^2} F_0(z)$. Once you have $F_0$, $F(z)=(1+z)F_0(z)$, obviously. –  Thomas Andrews Jul 25 '13 at 15:34
1  
Careful with your indices: you should get $F_1(z)=z+zF_0(z)$. –  Nicholas R. Peterson Jul 25 '13 at 15:46
    
@NicholasR.Peterson's objection is solved by defining $f_0=1$. That value is nowhere used in any later recurrence, so it is safe, we just have to ensure we subtract $1$ at the end. –  Thomas Andrews Jul 25 '13 at 16:03

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.