Euler-Binet Formula/Proof 4

Theorem

The Fibonacci numbers have a closed-form solution:

$F_n = \dfrac {\phi^n - \left({1 - \phi}\right)^n} {\sqrt 5} = \dfrac {\phi^n - \left({-1 / \phi}\right)^n} {\sqrt 5} = \dfrac {\phi^n - \left({-1}\right)^n\phi^{-n} } {\sqrt 5}$

where $\phi$ is the golden mean.

Putting $\hat \phi = 1 - \phi = -\dfrac 1 \phi$ this can be written:

$F_n = \dfrac {\phi^n - \hat \phi^n} {\sqrt 5}$

Proof

$G \left({z}\right) = \dfrac z {1 - z - z^2}$

Hence:

 $\displaystyle G \left({z}\right)$ $=$ $\displaystyle \dfrac z {1 - z - z^2}$ $\displaystyle$ $=$ $\displaystyle \dfrac 1 {\sqrt 5} \left({\dfrac 1 {1 - \phi z} - \dfrac 1 {1 - \hat \phi z} }\right)$ Partial Fraction Expansion

where:

$\phi = \dfrac {1 + \sqrt 5} 2$
$\hat \phi = \dfrac {1 - \sqrt 5} 2$
$\dfrac 1 {1 - \phi z} = 1 + \phi z + \phi^2 z^2 + \cdots$

and so:

$G \left({z}\right) = \dfrac 1 {\sqrt 5} \left({1 + \phi z + \phi^2 z^2 + \cdots - 1 - \hat \phi z - \hat \phi^2 z^2 - \cdots}\right)$

By definition, the coefficient of $z^n$ in $G \left({z}\right)$ is exactly the $n$th Fibonacci number.

That is:

$F_n = \dfrac {\phi^n - \hat \phi^n} {\sqrt 5}$

$\blacksquare$

Source of Name

This entry was named for Jacques Philippe Marie Binet and Leonhard Paul Euler.

Also known as

The Euler-Binet Formula is also known as Binet's formula.