Euler-Binet Formula/Proof 2

From ProofWiki
Jump to: navigation, search

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.