Euler-Binet Formula/Proof 4

From ProofWiki
Jump to navigation Jump to search

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

From Generating Function for Fibonacci Numbers, a generating function for the Fibonacci numbers is:

$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$

By Sum of Infinite Geometric Progression:

$\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.


Sources