4
$\begingroup$

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}$?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ – Karl Sep 9 '15 at 20:08
1
$\begingroup$

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) $$

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – user44400 Jan 14 '18 at 17:28
  • $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Jan 19 '18 at 9:04
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I want to use matrices and eigenvalues, but is there a way to avoid computing $PD^{n}P^{-1}$? $\endgroup$ – slezica Sep 9 '15 at 20:01
  • $\begingroup$ 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$. $\endgroup$ – Intelligenti pauca Sep 9 '15 at 20:19
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.