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

  1. Ceva's Theorem: A Matter of Appreciation
  2. When the Counting Gets Tough, the Tough Count on Mathematics
  3. I. Sharygin's Problem of Criminal Ministers
  4. Single Pile Games
  5. Take-Away Games
  6. Number 8 Is Interesting
  7. Curry's Paradox
  8. A Problem in Checker-Jumping
  9. Fibonacci's Quickies
  10. Fibonacci Numbers in Equilateral Triangle
  11. Binet's Formula by Inducion
  12. Binet's Formula via Generating Functions
  13. Generating Functions from Recurrences
  14. Cassini's Identity
  15. Fibonacci Idendtities with Matrices
  16. GCD of Fibonacci Numbers
  17. Binet's Formula with Cosines
  18. Lame's Theorem - First Application of Fibonacci Numbers

|Contact| |Front page| |Contents| |Games| |Up| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62087072

Search by google: