# Using linear algebra, how is the Binet formula (for finding the nth Fibonacci number) derived?

If possible, please refrain from any type of proof besides linear algebra. So, using the recursion formula $F_{n+1} = F_{n-1} + F_n$, for $n\gt 1$, and where $F_0 = 0$ and $F_1 = 1$, and the Fibonacci matrix, derive the golden ratio and ultimately the Binet formula.

-
–  lhf Apr 22 '12 at 20:05
I haven't done eigenvectors yet (I do that in about a week in my L.A. course). Is there a way to derive all that without using those concepts? –  Nico Bellic Apr 22 '12 at 20:08
You could use the shift operator $S$ in the space of sequences. Then $F$ satisfies $S^2 F=SF+F$ and so $(S^2-S-I)F=0$. You now factor $S^2-S-I$ to find its kernel. @BillDubuque has proposed this approach several times here but I can't find a good link right now. –  lhf Apr 22 '12 at 20:10
I'm truly, really sorry, but I'm not sure if I'm able to follow you. –  Nico Bellic Apr 22 '12 at 20:15
See for instance cs-netlab-01.lynchburg.edu/courses/algorithms/recurenc.htm (Example - solving the Fibonacci numbers) This is a random link found by Google. I could not find anything in Wikipedia. –  lhf Apr 22 '12 at 20:20

I am not sure to which extent this will be helpful for OP, but I'll post this anyway. This is basically the same solution as the one posted by Zhen Lin, but without any explicit reference to eigenvalues or eigenvectors.

So the sequence given by $F_{n+2}=F_{n+1}+F_n$ seems to be complicated. But there is a wide class of sequences we understand very good - geometric progressions.

Let us ask the question whether we can modify the sequence $F_n$ to get a geometric progression. E.g. we can ask whether there is an $x$ such that the sequcence $G_n=xF_n+F_{n-1}$ is a geometric progression.

From \begin{align} F_{n+1}&=F_n+F_{n-1}\\ F_{n}&=F_{n-1}+F_{n-2} \end{align} we get $$G_{n+1}=xF_{n+1}+F_n=xF_n+(x+1)F_{n-1}+F_{n-2}= xF_n+(x+1)F_{n-1}+F_n-F_{n-1}=(x+1)F_n+xF_{n-1}.$$ If we want the RHS to be a multiple of $G_n$, then we must have $$\frac{x+1}x=x,$$ i.e. $x+1=x^2$ or $x^2-x-1=0$, which has the two solutions $\lambda_{1,2}=\frac{1\pm\sqrt5}2$.

Notice that $\lambda_1+\lambda_2=1$, $\lambda_1\lambda_2=-1$.

For any of the above values we have $$G_{n+1}=(\lambda+1)F_n+\lambda F_{n-1}=\lambda\left(\frac{\lambda+1}\lambda F_n+F_{n-1}\right)=\lambda G_n.$$ We also have $G_1=\lambda$, $G_0=1$.

So we get \begin{align} \lambda_1F_{n}+F_{n-1}&=\lambda_1^n\\ \lambda_2F_{n}+F_{n-1}&=\lambda_2^n \end{align} If we subtract the above two equations, we get $$(\lambda_1-\lambda_2)F_{n}=\lambda_1^n-\lambda_2^n$$ which gives $$F_n=\frac{\lambda_1^n-\lambda_2^n}{\lambda_1-\lambda_2}.$$

In the solution, which used the diagonal form and eigenvalues, we did not have to guess, that it is possible to obtain geometric progressions combining Fibonacci sequence and shifted Fibonacci sequence - we get this fact from that diagonal matrix.

Or we can look at this the other way round - many applications of diagonal matrices similar to given matrix (e.g. in linear recurrences, ordinary differential equations) can be viewed as an effort to transform the original problem to a simpler form; in this case the simpler form was a geometric progression.

-

The Fibonacci numbers are defined by a second-order linear recurrence equation: $$F_{n+2} = F_{n+1} + F_n$$ This means we can treat the solution of $F_n$ in terms of $n$ as a problem in linear algebra involving only $2$-dimensional vectors. In some sense, what we are doing is modelling this as a dynamical process on a $2$-dimensional state space.

Let $V = \mathbb{R}^2$. We define a linear operator $T : V \to V$ by $$T(x, y) = (y, x + y)$$ Notice that $T(F_{n}, F_{n+1}) = (F_{n+1}, F_{n+2})$, so you can think of $V$ as being a sliding $2$-entry window on the Fibonacci sequence and $T$ as the operator which advances the window along the Fibonacci sequence. The initial conditions $F_0 = 0, F_1 = 1$ then imply that $$T^n(0, 1) = (F_n, F_{n+1})$$ so all we need to do to find $F_n$ in terms of $n$ is to find an effective way to compute iterates of the operator $T$!

Now, we get our hands dirty and represent $T$ as a matrix: $$T = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$$ Imagine if we could somehow find an invertible matrix $P$ and a diagonal matrix $D$ such that $T = P D P^{-1}$; then, by matrix algebra, we would have $T^n = P D^n P^{-1}$, and it is easy to compute powers of diagonal matrices. The theory of eigenvectors and eigenvalues gives us one way to find such a factorisation of $T$. Notice that $$\det (T - x I) = \det (P(D - x I)P^{-1}) = (\det P)(\det (D - x I))(\det P^{-1}) = \det (D - x I)$$ but a simple calculation shows $$\det (D - x I) = \det \begin{pmatrix} \lambda_1 - x & 0 \\ 0 & \lambda_2 - x \end{pmatrix} = (\lambda_1 - x)(\lambda_2 - x)$$ so whatever $\lambda_1$ and $\lambda_2$ are, they must be the zeros of the polynomial $$\det (T - x I) = \det \begin{pmatrix} -x & 1 \\ 1 & 1 - x \end{pmatrix} = x^2 - x - 1$$ which, surprise surprise, is the minimal polynomial of the golden ratio. So let $\lambda_1 = \frac{1}{2} (1 + \sqrt{5})$ and $\lambda_2 = \frac{1}{2} (1 - \sqrt{5})$. These are the eigenvalues of $T$. By construction, $\det (T - \lambda_1 I) = \det (T - \lambda_2 I) = 0$, so there must be non-zero vectors $\begin{pmatrix} x_1 \\ y_1 \end{pmatrix}$ and $\begin{pmatrix} x_2 \\ y_2 \end{pmatrix}$ such that $$T \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} = \lambda_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix}$$ $$T \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = \lambda_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix}$$ These vectors are called the eigenvectors of $T$. I leave you to verify that $x_1 = \lambda_1 - 1$, $y_1 = 1$, $x_2 = \lambda_2 - 1$, $y_2 = 1$ works, but there are other solutions.

Define the matrix $P$ by $$P = \begin{pmatrix} x_1 & x_2 \\ y_1 & y_2 \end{pmatrix}$$ Notice that $$\begin{pmatrix} x \\ y \end{pmatrix} = \alpha_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} + \alpha_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = P \begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix}$$ so by linearity we have $$T \begin{pmatrix} x \\ y \end{pmatrix} = \lambda_1 \alpha_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} + \lambda_2 \alpha_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = P \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix}$$ but we can invert $P$ to find $\alpha_1$ and $\alpha_2$ in terms of $x$ and $y$, so we have obtained the desired factorisation of $T$ as $P D P^{-1}$ with $D$ diagonal. Putting everything together, we get the formula $$T^n = P \begin{pmatrix} {\lambda_1}^n & 0 \\ 0 & {\lambda_2}^n \end{pmatrix} P^{-1}$$ and applying this to the vector $\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ gives Binet's formula.

-
The OP seems to want to avoid eigenvalue decompositions. –  lhf Apr 23 '12 at 1:09