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.
![](../gifs/tbow_sh.gif)
Fibonacci Numbers
- Ceva's Theorem: A Matter of Appreciation
- When the Counting Gets Tough, the Tough Count on Mathematics
- I. Sharygin's Problem of Criminal Ministers
- Single Pile Games
- Take-Away Games>
- Number 8 Is Interesting
- Curry's Paradox
- A Problem in Checker-Jumping
- Fibonacci's Quickies
- Fibonacci Numbers in Equilateral Triangle
- Binet's Formula by Inducion
- Binet's Formula via Generating Functions
- Generating Functions from Recurrences
- Cassini's Identity
- Fibonacci Idendtities with Matrices
- GCD of Fibonacci Numbers
- Binet's Formula with Cosines
- Lame's Theorem - First Application of Fibonacci Numbers
![](../gifs/tbow_sh.gif)
|Contact| |Front page| |Contents| |Games| |Up|
Copyright © 1996-2018 Alexander Bogomolny71551477