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!


Author: ficetea

I'll write more here later!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s