# Generating Function for Fibonacci Sequence

We seek closed form for the power series $\sum_{n=0}^\infty F_nz^n$, where $F_0 = 1$, $F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$. First we note that the ratio test yields

$\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_n}|z| = \varphi |z|$, where $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. Thus the series converges on the region of the complex plane where $|z| < \frac{1}{\varphi}$. Now let the power series be denoted by $F(z)$, and note that

$F(z) - zF(z) - z^2F(z) = 1 + \sum_{n=0}^\infty (F_{n+2}-F_{n+1}-F_n)z^{n+2} = 1$

and so $F(z) = \frac{1}{1-z-z^2}$. It seems so unlikely, before you know better at least, that things like that can be done. Why should it be that the nth Fibonacci number is given by $\frac{1}{2\pi i}\oint\frac{1}{z^{n+1}(1-z-z^2)}dz$, the integral along some closed contour in the complex plane of a function that otherwise seems unrelated. That’s maths!