# Fibonacci sequence and eigenvalues

I'm learning about eigenvectors and values, and one of the excercises in my book tackles the fibonacci recursion from this angle.

Let $F = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n \quad\text{ then }\quad \begin{bmatrix}x_{n+1}\\x_n\end{bmatrix} = F^n \begin{bmatrix}x_1\\x_0\end{bmatrix}$

To obtain a closed formula for $x_n$, I've obtained the eigenvalues and vectors of $F$, diagonalized it into $PDP^{-1}$ (where $P$ is the eigenvector matrix and $D$ is $\operatorname{diag}(\operatorname{eig}(F))$ and calculated the product of $PD^nP^{-1}$.

I feel like I'm missing something. The eigenvalues are there in the closed formula. Is there a way to deduce the formula from the eigenvalues without calculating $P^{-1}$ and $PDP^{-1}$?

• If I understand correctly you are decoupling the system and inevitably divide through by the eigenvalues for each separate equation because of the diagonal matrix. I think (not sure) this is misleading because it suggests the system could've been solve straight away. I've recently thought about this so myself so I apologize if my comments are wrong. – Karl Sep 9 '15 at 20:08

No, you don't need to explicitly compute $P^{-1}$ and multiply out $PD^nP^{-1}$ in order to get the closed formula for the Fibonacci numbers, but if you avoid it you still need to do something similar.

Call that matrix $A=(\begin{smallmatrix}1&1\\1&0\end{smallmatrix})$ (for some reason the question puts $x_{n+1}$ above $x_n$ in the column vector, so everything will be turned upside down: the normal thing would have been to put it below, and use the matrix $(\begin{smallmatrix}0&1\\1&1\end{smallmatrix})$ instead). Its eigenvalues $\phi_+=\frac{1+\sqrt5}2$ and $\phi_-=\frac{1-\sqrt5}2$, and choose eigenvectors for each of these eigenvalues: $v=(\begin{smallmatrix}\phi_+\\1\end{smallmatrix})$ and $w=(\begin{smallmatrix}\phi_-\\1\end{smallmatrix})$; your change of basis matrix $P$ is then formed by taking the coordinates of $v,w$ as columns: $P=(\begin{smallmatrix}\phi_+&\phi_-\\1&1\\\end{smallmatrix})$. The fact that $v$ and $w$ are eigenvectors means that you know the general expression for the terms of sequences $(a_n)_{n\in\Bbb N}$ and $(b_n)_{n\in\Bbb N}$, defined using the same recurrence relation as for the Fibonacci sequence, but contrary to it with the special initial conditions $a_0=1,a_1=\phi_+$ respectively $b_0=1,b_1=\phi_-$: from $A^n\cdot v=\phi_+^nv$ for all $n$ one gets $a_n=\phi_+^n$, and from $A^n\cdot w=\phi_-^nw$ one gets $b_n=\phi_-^n$ (the formula leaves nothing but the power of the eigenvalue because our eigenvectors were conveniently chosen to have bottom entry equal to$~1$).

But the Fibonacci sequence $(f_n)_{n\in\Bbb N}$ has initial values $f_0=0$ and $f_1=1$, so you want to know (the bottom entry of) the matrix product $A^n\cdot(\begin{smallmatrix}1\\0\end{smallmatrix})$ for any$~n$. Since multiplication by $A^n$ is linear, we can find this by writing $(\begin{smallmatrix}1\\0\end{smallmatrix})$ as a linear combination of $v$ and $w$; then the expression for $f_n$ will be the corresponding linear combination of $v$ and $w$. The relation $\mu v+\nu w=(\begin{smallmatrix}0\\1\end{smallmatrix})$ can be written as $P\cdot(\begin{smallmatrix}\mu\\\nu\end{smallmatrix})=(\begin{smallmatrix}1\\0\end{smallmatrix})$ and is a $2\times2$ linear system of equations. The solution is $(\begin{smallmatrix}\mu\\\nu\end{smallmatrix})=P^{-1}\cdot(\begin{smallmatrix}1\\0\end{smallmatrix})$, but can be found using Gaussian elimination without computing $P^{-1}$: the result is $\mu=\frac1{\sqrt5}$ and $\nu=-\frac1{\sqrt5}$. Then finally $$f_n=\mu\phi_+^n+\nu\phi_-^n = \frac1{\sqrt5}\left((\frac{1+\sqrt5}2)^n-(\frac{1-\sqrt5}2)^n\right)$$

• The vectors $v=(\begin{smallmatrix}1\\\phi_+\end{smallmatrix})$ and $w=(\begin{smallmatrix}1\\\phi_-\end{smallmatrix})$ are not Eigenvectors for $\phi_+$ and $\phi_-$, respectively, but the vectors $v'=(\begin{smallmatrix}-1\\\phi_+\end{smallmatrix})$ and $w'=(\begin{smallmatrix}-1\\\phi_-\end{smallmatrix})$ are. – user44400 Jan 14 '18 at 17:28
• @user44400 Thank you for pointing out my error. The real point is that I missed that the problem statement turns vectors upside down with respect to what would be a normal convention, which I had missed upon reading. My answer is now corrected and addresses this point. – Marc van Leeuwen Jan 19 '18 at 9:04

A proof of Binet's formula which doesn't make use of matrices can be found here: http://www.cut-the-knot.org/proofs/BinetFormula.shtml.

• I want to use matrices and eigenvalues, but is there a way to avoid computing $PD^{n}P^{-1}$? – slezica Sep 9 '15 at 20:01
• If you want to compute a single $x_n$ then you can simply calculate $F^n\begin{bmatrix}x_1\\x_0\end{bmatrix}$. This however is not suited to finding a closed formula. That can be done instead using $D$, because for the elements of $D^n$ an explicit expression is available. In other words: $PD^nP^{-1}$ is only a convenient way to find an explicit form for $F^n$. – Intelligenti pauca Sep 9 '15 at 20:19

Caution I decided to include the following because it was too long for a comment. I believe it to be correct but I'm not 100%. If appropriate I will delete / edit

Let $\boldsymbol{b}=\begin{bmatrix}x_{n+1}\\x_n\end{bmatrix}$ and $\boldsymbol{x} = \begin{bmatrix}x_1\\x_0\end{bmatrix}$

You have the system $\boldsymbol{b} = F^n \boldsymbol{x}$

Form the matrix $P$ whose columns are the eigenvectors of $F$.

Use the substitution $\boldsymbol{x}=P\boldsymbol{u}$ where $\boldsymbol{u}$ is a column vector.

You now have $$\boldsymbol{b} = F^n \boldsymbol{x}\\\boldsymbol{b} = F^n P\boldsymbol{u}\\P^{-1}\boldsymbol{b} = P^{-1}F^n P\boldsymbol{u}\\P^{-1}\boldsymbol{b}=D^n\boldsymbol{u}$$

Where $D$ is a matrix whose diagonal elements are the eigenvalues of $F$

As the $D$ is diagonal the system of equations is decoupled and solvable separately.

I believe you are asking that, as the components of $\boldsymbol{u}$ inevitably end up multiplied by the powers of eigenvalues, is there a short cut? I don't know of any direct method.

Hope it helps the discussion anyways.