For example, from the sequence $f_n=2f_{n-1}+\frac{1}{2}f_{n-2}$ and starting elements $f_0=f_1=1$ I derived the generating function $F=\frac{1-x-x^2}{1-2x-\frac{1}{2}x^2}$

How would I reverse the process and derive $f_n$ given just the generating function?

Edit: My $F$ is wrong. Right value should be $F=\frac{1-x}{1-2x-\frac{1}{2}x^2}$

  • $\begingroup$ Is that $F$ right? $\endgroup$ Commented Sep 10, 2017 at 18:41
  • $\begingroup$ I think so. I can update my question with how I found it, if you wish $\endgroup$ Commented Sep 10, 2017 at 18:43
  • $\begingroup$ Can you see any similarity between the denominator and the recursive relationship? $\endgroup$
    – Math Lover
    Commented Sep 10, 2017 at 18:44
  • $\begingroup$ @MathLover Wow, it's very obvious actually. Can't believe I missed that. How does the numerator figure in though? And is there a way to get $f_n$ from $F$ in a formula not dependant on $f_{n-1}$ and $f_{n-2}$ $\endgroup$ Commented Sep 10, 2017 at 18:47
  • $\begingroup$ Factor the denominator into linear factors, then expand using partial fractions, then recognize the terms as generating functions e.g. $\frac{\alpha}{1 - \beta x} = \sum_{n=0}^\infty \alpha \beta^n x^n$. $\endgroup$ Commented Sep 10, 2017 at 19:02

1 Answer 1


$F$ is wrong. Anyway suppose that the right was $F(x)=\dfrac{x-1}{\frac{x^2}{2}+2 x-1}$

You have to expand it in MacLaurin series: $$F(x)=\sum _{n=0}^{\infty } f_n x^n$$ $f_n$ will be the solution

Hope this helps


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .