Euler-Binet Formula/Proof 2
Jump to navigation
Jump to search
![]() | 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.