# How to derive the general element of a sequence from its generating function?

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}$

• Is that $F$ right? Commented Sep 10, 2017 at 18:41
• I think so. I can update my question with how I found it, if you wish Commented Sep 10, 2017 at 18:43
• Can you see any similarity between the denominator and the recursive relationship? Commented Sep 10, 2017 at 18:44
• @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}$ Commented Sep 10, 2017 at 18:47
• 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$. Commented Sep 10, 2017 at 19:02

$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