# 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?

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

• Easily the simplest approach. Thus, 6765. – Did Feb 6 '14 at 17:50

You can do the following:

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

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

3. $\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})}$

4. 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$.

1. Add the two series and you are done.
• Could you expand step 4? I can't quite see what is going on. – marshall Feb 6 '14 at 13:08

If you calculate $F(0.01)$ in Windows calculator you'll get $0.010102030508132134559046368320032$. Look at pairs of digits and you'll see you get the Fibonacci sequence right up until it gets into the 3-digit range.

So a simplistic way to do it is to calcuate $F(10^{-5})$ to something like 105 digits of accuracy.

$F(10^{-5}) \approx 0.00001 00001 00002 00003 00005 00008 00013 00021 00034 00055 00089 00144 00233 00377 00610 00987 01597 02584 04181 06765 10946$

Looking at this, the twentieth 5-digit group is $06765$, which is indeed $f_{20}$.

You can also accomplish it with infinite precision integers.

$$F(10^{-a}) = \dfrac{10^{-a}}{1 - 10^{-2a} - 10^{-a}} = \dfrac{10^a}{10^{2a} - 1 - 10^a}$$

Using the fact that $f_n < 10^n$,

$$f_n = \lfloor 10^{n^2}F(10^{-n}) \rfloor \mod 10^n$$ $$= \left\lfloor \dfrac{10^{n^2+n}}{10^{2n} - 1 - 10^n}\right\rfloor \mod 10^n$$

But who says we have to use decimals here? $f_n < 2^n$ too, and the following holds for $n > 1$.

$$f_n = \left\lfloor \dfrac{2^{n^2+n}}{2^{2n} - 1 - 2^n}\right\rfloor \mod 2^n$$

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.

• Why did you need to find the partial fraction decomposition first? – marshall Feb 6 '14 at 13:11
• @marshall because it makes differentiation easier, if you seek a closed form in $n$ for $\partial_z^n (z-\alpha)^{-1}(z-\beta)^{-1}$ you will run into trouble, because the product rule will make the expression more complicated with each step, but in the decomposed form you can use $\partial_z^n(z-\alpha)^{-1}=(-1)^n n! (-\alpha)^{-n-1}$ which follows from simple induction. – flonk Feb 6 '14 at 14:35
• I know this is a dim question.. but if I take the third derivative of $f(x) = x/(1-x-x^2)$ and evaluate it at $x=0$ I get $12$ which isn't right. Why is this? – marshall Feb 6 '14 at 17:12
• @marshall I have to correct myself, multiplying the generator with $x$, i.e. $G(x)\to xG(x)$ corresponds to shifting the sequence $a_n\to a_{n+1}$, so it is still odd that you get $12$ which is not a Fibonacci number. – flonk Feb 10 '14 at 8:25
• @marshall OK, now I resolved it, I stupidly forgot the factorial, i.e. $a_N = f^{(N)}(0)/N!$, not $f^{(N)}(0)$. In your case it gives $12/3!=2$. – flonk Feb 10 '14 at 20:58