Fibonacci numbers

The Fibonacci numbers $F_i$, for some $i\in {\mathbb{Z}}_{\ge 0}$, as the numbers:

$$F_n=\{\begin{array}{ll}0& \text{if}n=0\\ 1& \text{if}n=1\\ F_{n-1}+F_{n-2}& \text{if}n\ge 2\end{array}$$

i.e., the $i$-th Fibonacci number is the sum of the two previous ones. This yields the sequence:

$$0,1,1,2,3,5,8,13,21,34,55,\dots$$

As it turns out, we can also define the $i$-th number with a closed-form expression, Binet’s formula:

$$F_n=\frac{{\phi }^n-{\psi }^n}{\phi -\psi }=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}}$$

where $\phi$ is the golden ratio, and $\psi$ is its conjugate:

$$\phi =\frac{1+\sqrt{5}}{2}\approx 1.61803$$ $$\psi =\frac{1-\sqrt{5}}{2}=1-\phi \approx -0.61803$$

This has many proofs, some of which are explored below.

Matrix proof

If we define some matrix $A$ such that:

$$A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$ $$A^n=\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n+1}\end{array}\right]$$ $$A^n{\vec{e}}_1=\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]$$

The problem is that this is still a recursive difference equation expression. We note, by theorem, that we could find a basis that diagonalises $A$, such that:

$$A^n=S{B}^n{S}^{-1}$$ $$B^n=\left[\begin{array}{cc}{\lambda }_1^n& 0\\ 0& {\lambda }_2^n\end{array}\right]$$

i.e., we can find the eigenvalues of $A$. Our characteristic polynomial is given by:

$$0={\lambda }^2-\lambda -1$$

i.e., we have:

$${\lambda }_1=\frac{1+\sqrt{5}}{2}$$ $${\lambda }_2=\frac{1-\sqrt{5}}{2}$$

i.e., the golden ratio and its conjugate. As it turns out, the eigenvectors of $A$ are given by:

$${\vec{v}}_1=\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right]$$ $${\vec{v}}_2=\left[\begin{array}{c}{\lambda }_2\\ 1\end{array}\right]$$

If we say that:

$$F_n={\vec{e}}_2^T{A}^n{\vec{e}}_1$$

then from our expression for $A$, we get a closed form expression for $F_n$ where:

$$F_n=\frac{{\lambda }_1^n-{\lambda }_2^n}{{\lambda }_1-{\lambda }_2}$$

which is as stated above.

Induction proof