# 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

$\map G z = \dfrac z {1 - z - z^2}$

Hence:

 $\displaystyle \map G z$ $=$ $\displaystyle \dfrac z {1 - z - z^2}$ $\displaystyle$ $=$ $\displaystyle \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \phi z} - \dfrac 1 {1 - \hat \phi z} }$ 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:

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

By definition, the coefficient of $z^n$ in $\map G z$ 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.