Fibonacci sequence formula using generating functions

Question

This is the generating function for the fibonnaci sequence:

$$F(x) = \frac{x}{1 - x - x^{2} }$$

I need to get the sequence to find any element from this sequence directly. So I'm trying to find an $x$ coefficient:

$$F(x) = \frac{x}{1 - x - x^{2} } = \frac{x}{(1 - x y_{-})(1 - x y_{+}) } $$

1) I know quadratic equations can be written as $(x - x_{1})(x + x_{2})$, but here it's written differently - does this work for every quadratic equation?

$$F(x) = \frac{1}{(x_{1} - x_{2})}\left(\frac{1}{(1-xx_{1})} - \frac{1}{(1-xx_{2})}\right)$$

This step is understood.

$$F(x) = \frac{1}{\sqrt{5}}\left(\sum{x_{1}}^{n}{x}^{n} - \sum{x_{2}}^{n}{x}^{n}\right)$$

2) What happens here? How come that the epsilons have appeared here?

The next step is to take out the coefficients, it's not difficult so I understand this part.

Answer 1

If you want the sequence $\{1,1,2,3,5,...\}$ as fibonacci sequence, then the generating function is: $$F(x)=\frac{1}{1-x-x^2}$$$$=-\frac{1}{(x_1-x)(x_2-x)}.$$ Otherwise, see another answer. It does not make much difference. Just multiply by $x$. \Then this is same as your decomposition, just done differently. After this, after partial fraction decomposition, you will get that both coefficients are equal and in fact are equal to $-\frac{1}{x_1-x_2}$. To understand this, try the partial fraction decomposition. $$=\frac{1}{x_1-x_2}\left(\frac{1}{x_1-x}-\frac{1}{x_2-x}\right)$$ From here, you take $$\frac{1}{x_1-x}=\frac{1}{\frac{1}{x_1}}\frac{1}{1-\frac{x}{x_1}}$$ Treat this as geometric series so that $\frac{x}{x_1}\le 1$ $$=\frac{1}{x_1-x_2}\sum_{i=0}^{\infty}\left(\frac{x^i}{x_1^{i+1}}-\frac{x^i}{x_2^{i+1}}\right)$$ In the initial factorisation with $x_1$ and $x_2$, you should have obtained roots as $$x_1=-\frac{1-\sqrt{5}}{2};x_2=-\frac{1+\sqrt{5}}{2}$$Thus you have $$\sum_{i=0}^{\infty}\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{i+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{i+1}\right)x^i$$

Answer 2

Well, given a function $$F(x) = \frac{x}{1-x-x^2}$$ you would like to find the sequence $a_n$ such that $F(x) = \sum_{n=0}^\infty a_n x^n$ (i.e. the Maclaurin series).

Multiplying by $x$ is easy, so you want to represent $\frac{1}{1-x-x^2}$ as something of which you may know the series representation for. A natural choice is the geometric series $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$.

So now, you would like to decompose $$\frac{1}{1-x-x^2} = \frac{A}{1-x\cdot x_+} + \frac{B}{1-x\cdot x_-}.$$

(Find which $x_+$ and $x_-$ are the magic ones that work, and get $A,B$ as well.)

Now

$$F(x) = \frac{x}{1-x-x^2} = \frac{Ax}{1-x\cdot x_+} + \frac{Bx}{1-x\cdot x_-} = Ax \sum_{n=0}^\infty x_+^n x^n + Bx \sum_{n=0}^\infty x_-^n x^n = \sum_{n=0}^\infty \left(A x_+^n + B x^n_-\right) x^{n+1} $$

from where you can easily read off the coefficients you want.