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

Golden Ratio in Geometry

71924446