Euler-Binet Formula/Proof 2

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

Let $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$.

First by the lemma to Cassini's Identity:

$(1): \quad \forall n \in \Z_{>1}: A^n = \begin{bmatrix} F_{n + 1} & F_n \\ F_n & F_{n - 1} \end{bmatrix}$

Next is is demonstrated that $A$ has the eigenvalues $\phi$ and $\hat \phi$, where $\hat \phi = 1 - \phi$.

Now we have that:

\((2):\quad\)

\(\displaystyle A \begin{pmatrix} \phi \\ 1 \end{pmatrix}\)

\(=\)

\(\displaystyle \begin{pmatrix} \phi + 1 \\ \phi \end{pmatrix}\)

$\quad$

$\quad$

\(\displaystyle \)

\(=\)

\(\displaystyle \phi \begin{pmatrix} \phi \\ 1 \end{pmatrix}\)

$\quad$ since $\phi$ is a solution of $x^2 - x - 1 = 0$

$\quad$

\(\displaystyle A \begin{pmatrix} \hat \phi \\ 1 \end{pmatrix}\)

\(=\)

\(\displaystyle \begin{pmatrix} \hat \phi + 1 \\ \hat \phi \end{pmatrix}\)

$\quad$

$\quad$

\(\displaystyle \)

\(=\)

\(\displaystyle \hat \phi \begin{pmatrix} \hat \phi \\ 1 \end{pmatrix}\)

$\quad$ since $\hat \phi$ is a solution of $x^2 - x - 1 = 0$

$\quad$

This shows that:

$\displaystyle \begin{pmatrix} \phi \\ 1 \end{pmatrix}$ is an eigenvector of $A$ with eigenvalue $\phi$

and:

$\displaystyle \begin{pmatrix} \hat \phi \\ 1 \end{pmatrix}$ is an eigenvector of $A$ with eigenvalue $\hat \phi$.

Thus:

$\displaystyle \begin{pmatrix} \frac \phi {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}$ is an eigenvector of $A$ with eigenvalue $\phi$

and:

$\displaystyle \begin{pmatrix} \frac {\hat \phi} {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}$ is an eigenvector of $A$ with eigenvalue $\hat \phi$.

By Eigenvalue of Matrix Powers we get for a positive integer $n$:

\(\displaystyle \phi^n \begin{pmatrix} \frac \phi {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}\)

\(=\)

\(\displaystyle A^n \begin{pmatrix} \frac \phi {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}\)

$\quad$

$\quad$

\(\displaystyle {\hat \phi}^n \begin{pmatrix} \frac {\hat \phi} {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}\)

\(=\)

\(\displaystyle A^n \begin{pmatrix} \frac {\hat \phi} {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}\)

$\quad$

$\quad$

From $(1)$ we get:

$A^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} F_{n + 1} \\ F_n \end{pmatrix}$

Substituting:

$\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} \frac \phi {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix} - \begin{pmatrix} \frac {\hat \phi} {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}$

we get:

\(\displaystyle \begin{pmatrix} F_{n + 1} \\ F_n \end{pmatrix}\)

\(=\)

\(\displaystyle \frac 1 {\sqrt 5} A^n \left({\begin{pmatrix} \phi \\ 1 \end{pmatrix} - \begin{pmatrix} \hat \phi \\ 1 \end{pmatrix} }\right)\)

$\quad$

$\quad$

\(\displaystyle \)

\(=\)

\(\displaystyle A^n \begin{pmatrix} \frac \phi {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix} - A^n \begin{pmatrix} \frac {\hat \phi} {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}\)

$\quad$

$\quad$

\(\displaystyle \)

\(=\)

\(\displaystyle \phi^n \begin{pmatrix} \frac \phi {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix} - \hat \phi^n \begin{pmatrix} \frac {\hat \phi} {\sqrt 5} \\ \frac 1 {\sqrt 5} \end{pmatrix}\)

$\quad$

$\quad$

\(\displaystyle \)

\(=\)

\(\displaystyle \frac 1 {\sqrt 5} \begin{pmatrix} \phi^n \cdot \phi - \hat \phi^n \cdot \hat \phi \\ \phi^n - \hat \phi^n \end{pmatrix}\)

$\quad$

$\quad$

Hence the result.

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