How to use the generating function $F(x) =x/(1-x-x^2).$ The generating function for the Fibonacci sequence is
$$F(x) =x/(1-x-x^2).$$
To work out the 20th value of the sequence I understand you somehow expand this and look at the coefficient of $x^{20}$.  How exactly do you do this?
 A: \begin{eqnarray*}
{z\over 1-z-z^2}&=&z\sum_{k=0}^\infty (z+z^2)^k\\
 &=&z\sum_{k=0}^\infty z^k(1+z)^k\\
&=&z\sum_{k=0}^\infty z^k \sum_{j=0}^k {k\choose j} z^j\\
&=&\sum_{k=0}^\infty \sum_{j=0}^k {k\choose j} z^{1+j+k}
\end{eqnarray*}
From this we see that the coefficient of $z^N$ is 
$$\sum_{j=0}^{N-1}{N-1-j\choose j},$$
in particular the coefficient of $z^{20}$ is 
$${19\choose 0}+{18\choose 1}+{17\choose 2}+\cdots+{10\choose 9}.$$
A: You can do the following:


*

*Solve the equation $1-x-x^2=0$. The roots are $\frac{-1-\sqrt{5}}{2}$  and $\frac{-1+\sqrt{5}}{2}$.

*Then you have $1-x-x^2=-(x-\frac{-1-\sqrt{5}}{2})(x-\frac{-1+\sqrt{5}}{2})=-(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})$

*$\frac{-x}{(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})}=\frac{A}{(x+\frac{1+\sqrt{5}}{2})}+\frac{B}{(x+\frac{1-\sqrt{5}}{2})}$

*Find A and B then you can expand both fractions in geometric series. 
$\frac{-x}{(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})}=\frac{Ax+Bx+A\frac{1-\sqrt{5}}{2}+B+\frac{1+\sqrt{5}}{2}}{(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})}=\frac{(A+B)x+A\frac{1-\sqrt{5}}{2}+B\frac{1+\sqrt{5}}{2}}{(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})}$
Then  $(A+B)=-1$ and $A\frac{1-\sqrt{5}}{2}+B\frac{1+\sqrt{5}}{2}=0$
This s system gives  $A$ and $B$.


*

*Add the two series and you are done.

A: First, find the roots of your functions denominator $1-z-z^2$ which are 
$$z_\pm=-\frac{1\pm\sqrt{5}}{2}$$
Then find the partial fraction decomposition
$$\frac{z}{1-z-z^2}=\frac{z}{(z-z_-)(z-z_+)}=\frac{a}{z-z_+}+\frac{b}{z-z_-}$$
which turns out to be $a=\tfrac{1}{2}(1-\tfrac{1}{\sqrt{5}})$ and $b=\tfrac{1}{2}(1+\tfrac{1}{\sqrt{5}})$
Now you can easily compute the $N$th derivative of the function which at $z=0$ tells you the coefficient $a_N$:
$$a_N=\frac{1}{N!}\partial_z ^N f(z)|_{z=0}=\frac{1}{N!}\partial_z^N\left(\frac{a}{z-z_+}+\frac{b}{z-z_-}\right)_{z=0}=-\frac{1}{2}\left( \frac{a}{z_+^{N+1}}+\frac{b}{z_-^{N+1}}\right)$$
Plugging in $a$, $b$ from above and $N=20$ tells you the result.
