# Generating Functions - Fibonacci sequence

I'm new to generating functions, and my lecture showed how to obtain exact closed form expression for Fibonacci numbers.

The coefficients of the generating function F(x) is the Fibonacci sequence {f_n}. After some manipulation,

\begin{align} (1-x-x^2)F(x) &= x \tag{A} \\ \\ F(x) &= \frac{x}{1-x-x^2} \tag{B} \\ \\ F(x) &= \frac{\frac{A}{1-a_1x}+\frac{B}{1-a_2x}}{\sqrt 5} \tag{C} \\ \\ F(x) &= \sum_{n=0} f_nx^n \tag{D} \end{align}

After doing the partial fraction decomposition, F(x) can then be written as a sum of 2 geometric series the coefficients of the series can be read off to obtain the closed form expression.

The equality in the first line is between formal power series; and the equality in the following lines is in terms of the function. I struggling to understand how the second line follows the first line.

Can someone please explain the sense of the steps?

• when you say you don't get how the "second line follows from the first line", did you mean how the "third line follows from the second line"? If not, the result is trivial (as I share in my answer... unless you are counting from 0, which is an odd thing to do here. Perhaps line numbers would help?). Oct 3, 2015 at 4:15
• I guess I just want to know if all the items in the lines should be viewed as are formal power series or functions. Oct 3, 2015 at 4:36
• Thanks I meant the trivial one result like you posted. Oct 3, 2015 at 4:37
• The only lines I don't follow are $$F(x)=\frac{x}{1-x-x^2}$$ $$=F(x)=\frac{1}{\frac{1}{1-a_2}-\frac{\sqrt{5}}{1-a_1}}$$ What intermediate steps are there, because this is a massive leap. Oct 3, 2015 at 4:44
• Sorry there was a typo I edited the line. Oct 3, 2015 at 5:01

The solutions to $1-y-y^2=0$ are $A=(1+\sqrt 5)/2$ and $B=(1-\sqrt 5)/2$.Therefore for all $x$ we have $1-x-x^2=(1-x/A)(1-x/B)$. Then for $A \ne x \ne B$ we have $$\frac {1}{1-x-x^2}=$$ $$\frac {1}{(1-x/A)(1-x/B)}=$$ $$\left( \frac {1/A}{1-x/A}- \frac {1/B}{1-x/B} \right) \frac{1}{1/A-1/B}$$ which simplifies a little because $1/A-1/B=(B-A)/AB$ and $B-A=-\sqrt 5$ and $AB=-1$
The second line follows the first line by division. You simply divide both sides by $(1-x-x^2)$