Theorem: Euler-Binet Formula

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} = \dfrac {\phi^n - \paren {1 - \phi}^n} {\phi - \paren {1 - \phi}}$
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}$
From {{Defof|Golden Mean|index = 2}}: $\phi = \dfrac {1 + \sqrt 5} 2$
Therefore, substituting $\sqrt 5 = 2\phi - 1 = \phi - \paren {1 - \phi} = \phi - \hat \phi$, the above can be written as:
:$F_n = \dfrac {\phi^n - \hat \phi^n} {\paren {\phi - \hat \phi}}$

Proof:
Let $A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$.
First by {{Lemma|Cassini's Identity|proof = yes}}:
:$(1): \quad \forall n \in \Z_{>1}: A^n = \begin {bmatrix} F_{n + 1} & F_n \\ F_n & F_{n - 1} \end{bmatrix}$
Recall from Eigenvalues of Real Square Matrix are Roots of Characteristic Equation, we can find the eigenvalues of $\mathbf A$ by solving the equation $\map \det {\mathbf A - \lambda \mathbf I} = 0$
Therefore, taking the determinant of the square matrix below:
:$\mathbf A - \lambda \mathbf I = \begin {bmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{bmatrix}$
We obtain the equation:
{{begin-eqn}}
{{eqn | l = 0
      | r = -\lambda \paren {1 - \lambda} - 1
      | c = Determinant of Matrix Product
}}
{{eqn | r = \lambda^2 - \lambda - 1
      | c =
}}
{{eqn | r = \lambda^2 - \lambda + \paren {\lambda \phi - \lambda \phi} + \paren {\phi - \phi} - 1
      | c = adding 0
}}
{{eqn | r = \lambda^2 - \lambda + \paren {\lambda \phi - \lambda \phi} + \phi - \paren {\phi + 1}
      | c = regrouping
}}
{{eqn | r = \lambda^2 - \lambda + \paren {\lambda \phi - \lambda \phi} + \phi - \phi^2
      | c = Square of Golden Mean equals One plus Golden Mean
}}
{{eqn | r = \lambda^2 - \lambda \paren {1 - \phi} - \lambda \phi + \phi \paren {1 - \phi}
      | c = 
}}
{{eqn | r = \paren {\lambda - \phi} \paren {\lambda - \paren {1 - \phi} }
}}
{{end-eqn}}
Therefore, $A$ has the eigenvalues $\phi$ and $1 - \phi$. 
We will now determine the eigenvectors of $A$
{{Recall|Eigenvector of Real Square Matrix}}
{{:Definition:Eigenvector of Real Square Matrix}}
For $\lambda = \phi$, we have:
{{begin-eqn}}
{{eqn | l = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} v_1 \\ v_2 \end{bmatrix}
      | r = \begin{bmatrix} \phi v_1 \\ \phi v_2 \end{bmatrix}
      | c = 
}}
{{eqn | ll = \leadsto
      | l = \begin{bmatrix} v_1 + v_2 \\ v_1 \end{bmatrix}
      | r = \begin{bmatrix} \phi v_1 \\ \phi v_2 \end{bmatrix}
      | c = {{Defof|Matrix Product (Conventional)}}
}}
{{end-eqn}}
We see from the above, when $v_2 = 1$ then $v_1 = \phi$ and we have:
{{begin-eqn}}
{{eqn | l = \begin{bmatrix} \phi + 1 \\ \phi \end{bmatrix}
      | r = \begin{bmatrix} \phi^2 \\ \phi \end{bmatrix}
      | c = 
}}
{{eqn | r = \phi \begin{bmatrix} \phi \\ 1 \end{bmatrix}
      | c = 
}}
{{end-eqn}}
For $\lambda = 1 - \phi$, we have:
{{begin-eqn}}
{{eqn | l = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} v_1 \\ v_2 \end{bmatrix}
      | r = \begin{bmatrix} \paren {1 - \phi} v_1 \\ \paren {1 - \phi} v_2 \end{bmatrix}
      | c = 
}}
{{eqn | ll = \leadsto
      | l = \begin{bmatrix} v_1 + v_2 \\ v_1 \end{bmatrix}
      | r = \begin{bmatrix} \paren {1 - \phi} v_1 \\ \paren {1 - \phi} v_2 \end{bmatrix}
      | c = {{Defof|Matrix Product (Conventional)}}
}}
{{end-eqn}}
We see from the above, when $v_2 = 1$ then $v_1 = 1 - \phi$ and we have:
{{begin-eqn}}
{{eqn | l = \begin{bmatrix} 2 - \phi \\ 1 - \phi \end{bmatrix}
      | r = \begin{bmatrix} \paren {1 - \phi}^2 \\ 1 - \phi \end{bmatrix}
      | c = 
}}
{{eqn | r = \paren {1 - \phi} \begin{bmatrix} 1 - \phi \\ 1 \end{bmatrix}
      | c = 
}}
{{end-eqn}}
We have now demonstrated that:
:$\begin{bmatrix} \phi \\ 1 \end{bmatrix}$ is an eigenvector of $A$ with eigenvalue $\phi$
and:
:$\begin{bmatrix} 1 - \phi \\ 1 \end{bmatrix}$ is an eigenvector of $A$ with eigenvalue $1 - \phi$.
We now observe that:
{{begin-eqn}}
{{eqn | l = A^n \begin {bmatrix} 1 \\ 0 \end {bmatrix}
      | r = \begin {bmatrix} F_{n + 1} & F_n \\ F_n & F_{n - 1} \end {bmatrix} \begin {bmatrix} 1 \\ 0 \end {bmatrix}
      | c = from $(1)$ above
}}
{{eqn | r = \begin {bmatrix} F_{n + 1} \\ F_n \end {bmatrix}
      | c = {{Defof|Matrix Product (Conventional)}}
}}
{{end-eqn}}
Then we notice that:
{{begin-eqn}}
{{eqn | n = 2
      | l = \begin {bmatrix} 1 \\ 0 \end {bmatrix}
      | r = \frac 1 {\phi - \paren {1 - \phi} } \paren {\begin {bmatrix} \phi \\ 1 \end {bmatrix} - \begin {bmatrix} 1 - \phi \\ 1 \end {bmatrix} }
      | c = 
}}
{{end-eqn}}
From Eigenvalue of Matrix Power for a positive integer $n$, we have:
{{begin-eqn}}
{{eqn | l = A^n \begin{bmatrix} \phi \\ 1 \end{bmatrix}
      | r = \phi^n \begin{bmatrix} \phi \\ 1 \end{bmatrix}
      | c = $A^n \mathbf v = \lambda^n \mathbf v$
}}
{{eqn | l = A^n \begin{bmatrix} 1 - \phi \\ 1 \end{bmatrix}
      | r = \paren {1 - \phi}^n \begin{bmatrix} 1 - \phi \\ 1 \end{bmatrix}
      | c =  $A^n \mathbf v = \lambda^n \mathbf v$
}}
{{end-eqn}} 
Putting all of the pieces together, we obtain:
{{begin-eqn}}
{{eqn | l = \begin{bmatrix} F_{n + 1} \\ F_n \end{bmatrix}
      | r = A^n \begin{bmatrix} 1 \\ 0 \end{bmatrix}
}}
{{eqn | r = \dfrac 1 {\phi - \paren {1 - \phi} }  A^n \paren {\begin{bmatrix} \phi \\ 1 \end{bmatrix} - \begin{bmatrix} 1 - \phi \\ 1 \end{bmatrix} }
      | c = from (2) above
}}
{{eqn | r = \dfrac 1 {\phi - \paren {1 - \phi} }  \paren {A^n \begin{bmatrix} \phi \\ 1 \end{bmatrix} -  A^n \begin{bmatrix} 1 - \phi \\ 1 \end{bmatrix} }
      | c = 
}}
{{eqn | r = \dfrac 1 {\phi - \paren {1 - \phi} }  \paren {\phi^n \begin{bmatrix} \phi \\ 1 \end{bmatrix} -  \paren {1 - \phi}^n \begin{bmatrix} 1 - \phi \\ 1 \end{bmatrix} }
      | c = Eigenvalue of Matrix Power
}}
{{eqn | r = \dfrac 1 {\phi - \paren {1 - \phi} }  \paren {\begin{bmatrix} \phi^{n + 1} \\ \phi^n \end{bmatrix} -  \begin{bmatrix} \paren {1 - \phi}^{n + 1} \\ \paren {1 - \phi}^n \end{bmatrix} }
      | c = {{Defof|Matrix Product (Conventional)}}
}}
{{end-eqn}}
Hence the result.
{{qed}}