# Binet's Formula via Generating Functions

Fibonacci numbers that are defined recursively by

$F_n= \begin{cases} 0 & \mbox{if } n = 0; \\ 1 & \mbox{if } n = 1; \\ F_{n-1}+F_{n-2} & \mbox{if } n > 1. \\ \end{cases}$

can be calculated directly with Benet's formula:

$F_{n}=\frac{1}{\sqrt{5}}({\phi}^{n}-{\tau}^{n}).$

We already have two derivations of Binet's formula: one using a little of matrix algebra, the other by induction. Below I'll derive the formula from the generating function of the Fibonacci sequence:

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

The derivation is based on the formula for the sum of a geometric series - the generating function of the sequence $\{1, 1, 1, \ldots\}$:

$g(x)=\frac{1}{1-x}=1+x+x^{2}+x^{3}+\ldots$.

which we'll need in a little more general form:

$g(x)=\frac{1}{1-ax}=1+ax+a^{2}x^{2}+a^{3}x^{3}+\ldots$.

We shall apply the method of partial fractions to reduce the generating function $f(x)=\frac{x}{1-x-x^{2}}$ to a sum of two geometric series (This is in fact what Binet's formula is about.)

The equation $1-x-x^{2}=0$ has two roots: $-\frac{1+\sqrt{5}}{2}=-\phi$ and $-\frac{1-\sqrt{5}}{2}=-\tau$. Therefore,

$1-x-x^{2}=-(\phi +x)(\tau +x)=-\phi \tau(1-\tau x)(1-\phi x)=(1-\tau x)(1-\phi x)$,

because $\phi \tau = -1$. Now we shall determine coefficients $A$ and $B$ such that

$\frac{x}{1-x-x^{2}} = \frac{A}{1-{\tau}x} + \frac{B}{1-{\phi}x}=\frac{-x(\phi A + \tau B)+(A+B)}{(1-\tau x)(1-\phi x)}$.

Equating the numerators on both sides leads to two equations:

$A + B = 0$ and
$\phi A + \tau B = -1$.

Multiply the first equation by $\tau$ and subtract it from the second equation: $(\phi - \tau)A=-1$. Similarly, $(\phi - \tau)B=1$. Now, $\phi - \tau=\sqrt{5}$ which shows that

$f(x)=\frac{x}{1-x-x^{2}} = \frac{1}{\sqrt{5}}\big(\frac{1}{1-{\phi}x}-\frac{1}{1-\tau x}\big)$.

To these we may directly apply the formula for the sum of the geometric series, with the conclusion that

$F_{n}=[x^{n}]f(x) = \frac{1}{\sqrt{5}}({\phi}^{n}-{\tau}^{n})$,

which is exactly Binet's formula. ### Fibonacci Numbers 