Euler-Binet Formula/Proof 2

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Theorem

The Fibonacci numbers have a closed-form solution:

$F_n = \dfrac {\phi^n - \paren {1 - \phi}^n} {\sqrt 5} = \dfrac {\phi^n - \paren {-1 / \phi}^n} {\sqrt 5} = \dfrac {\phi^n - \paren {-1}^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:

\(\text {(2)}: \quad\)

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

\(=\)

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

\(\ds \)

\(=\)

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

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

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

\(=\)

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

\(\ds \)

\(=\)

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

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

This shows that:

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

and:

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

Thus:

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

and:

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

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

\(=\)

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

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

\(=\)

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

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:

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

\(=\)

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

\(\ds \)

\(=\)

\(\ds 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}\)

\(\ds \)

\(=\)

\(\ds \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}\)

\(\ds \)

\(=\)

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

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.