Euler-Binet Formula/Proof 2
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.
To discuss this in more detail, feel free to use the talk page.
Once you have done so, you can remove this instance of {{MissingLinks}} from the code.
Contents
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}\) | ||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \phi \begin{pmatrix} \phi \\ 1 \end{pmatrix}\) | since $\phi$ is a solution of $x^2 - x - 1 = 0$ | ||||||||||
| \(\displaystyle A \begin{pmatrix} \hat \phi \\ 1 \end{pmatrix}\) | \(=\) | \(\displaystyle \begin{pmatrix} \hat \phi + 1 \\ \hat \phi \end{pmatrix}\) | |||||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \hat \phi \begin{pmatrix} \hat \phi \\ 1 \end{pmatrix}\) | since $\hat \phi$ is a solution of $x^2 - x - 1 = 0$ |
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}\) | |||||||||||
| \(\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}\) |
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)\) | |||||||||||
| \(\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}\) | |||||||||||
| \(\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}\) | |||||||||||
| \(\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}\) |
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.
