Summary
The AMS Feature Column presents an elegant power-series derivation of Binet’s formula for the Fibonacci sequence. Instead of computing Fibonacci numbers recursively, the article introduces the generating function
$F(x)=\sum_{n=0}^{\infty}F_nx^n$.
Using the Fibonacci recurrence $F_n=F_{n-1}+F_{n-2}$ and shifting indices, the series satisfies
$F(x)=1+xF(x)+x^2F(x)$,
so
$F(x)=\frac{1}{1-x-x^2}$.
The denominator is connected to the two roots of the quadratic equation $x^2-x-1=0$. These roots involve the golden ratio
$\Phi=\frac{1+\sqrt5}{2}$
and its conjugate
$\Psi=\frac{1-\sqrt5}{2}$.
By decomposing the generating function into partial fractions and expanding the resulting terms as geometric series, the coefficient of $x^n$ is obtained:
$\boxed{F_n=\frac{\Phi^n-\Psi^n}{\sqrt5}}$.
This is Binet’s formula for the Fibonacci sequence.
Main mathematical ideas
The article provides a particularly nice connection between:
The central insight is that a recursive problem can be transformed into an algebraic problem by introducing a generating function. Once the generating function is known, extracting its coefficients produces an explicit formula for the entire sequence.
The article also demonstrates the power of the resulting formula by considering $F_{413}$, which is a 123-digit number. Rather than calculating hundreds of preceding Fibonacci numbers, Binet’s formula gives a direct route to the desired term.
ARTICLE / PDF
The AMS Feature Column presents an elegant power-series derivation of Binet’s formula for the Fibonacci sequence. Instead of computing Fibonacci numbers recursively, the article introduces the generating function
$F(x)=\sum_{n=0}^{\infty}F_nx^n$.
Using the Fibonacci recurrence $F_n=F_{n-1}+F_{n-2}$ and shifting indices, the series satisfies
$F(x)=1+xF(x)+x^2F(x)$,
so
$F(x)=\frac{1}{1-x-x^2}$.
The denominator is connected to the two roots of the quadratic equation $x^2-x-1=0$. These roots involve the golden ratio
$\Phi=\frac{1+\sqrt5}{2}$
and its conjugate
$\Psi=\frac{1-\sqrt5}{2}$.
By decomposing the generating function into partial fractions and expanding the resulting terms as geometric series, the coefficient of $x^n$ is obtained:
$\boxed{F_n=\frac{\Phi^n-\Psi^n}{\sqrt5}}$.
This is Binet’s formula for the Fibonacci sequence.
Main mathematical ideas
The article provides a particularly nice connection between:
- recurrence relations,
- formal power series,
- convergence,
- index shifting,
- partial fractions,
- geometric series,
- the quadratic formula, and
- the golden ratio.
The central insight is that a recursive problem can be transformed into an algebraic problem by introducing a generating function. Once the generating function is known, extracting its coefficients produces an explicit formula for the entire sequence.
The article also demonstrates the power of the resulting formula by considering $F_{413}$, which is a 123-digit number. Rather than calculating hundreds of preceding Fibonacci numbers, Binet’s formula gives a direct route to the desired term.
ARTICLE / PDF
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘