# Sequence analysis of the Fibonacci sequence using matrices?

1. Mar 29, 2010

### jspectral

1. The problem statement, all variables and given/known data
Using $$u_k = $\left( \begin{array}{ccc} F_{k+1} \\ F_k \end{array} \right)$$$ $$u_0 = $\left( \begin{array}{ccc} 1 \\ 0 \end{array} \right)$$$ $$A = $\left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array} \right)$$$
Solve for $$u_k$$ in terms of $$u_0$$ to show that:

$$F_k = \frac{1}{\sqrt{5}}\ \left(\left(\frac{1 + \sqrt{5}}{2}\ \right)^k - \left(\frac{1 - \sqrt{5}}{2}\ \right)^k\right)$$

2. Relevant equations
See above.
3. The attempt at a solution
Well, I worked out that $$u_k = A^k u_0$$
$$$\left( \begin{array}{ccc} F_{k+1} \\ F_k \end{array} \right)$$$ = $$$\left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array} \right)$^k$$ $$$\left( \begin{array}{ccc} 1 \\ 0 \end{array} \right)$$$

But I'm not sure of the matrix operations I need to use to expand that A matrix, and the other two, in order to obtain an algebraic expression.

Note: That 1,1,1,0 matrix is meant to be to the power of k, but the LaTex went weird.

2. Mar 29, 2010

### Dick

You need to find the eigenvalues and eigenvectors of A. Then express u0 as a combination of eigenvectors.

3. Mar 29, 2010

### jspectral

We haven't been taught eigenvalues/vectors yet. Is there any other method you can think of to do this problem?

4. Mar 29, 2010

### Dick

The only other way to do it that I can think of is to notice your sequence satisfies the recursion relation F_(k+2)=F_(k+1)+F_k. Now you look for exponential solutions by substituting F_k=C*p^k into that relation and solving for p. Since it's quadratic you get two solutions for p. Now combine them to fit the initial conditions. I'm not sure why you'd set it up with matrices if you aren't going to use eigenvectors, though.

5. Mar 30, 2010

### jspectral

Okay, so I got the eigenvalues of the matrix A as $$\left(\frac{1 \pm \sqrt{5}}{2}\ \right)$$

Now how do I use those eigenvalues with the power of k in order to obtain an expression for F_(k)?

6. Mar 30, 2010

### Dick

If v is an eigenvector of your matrix M with eigenvalue r, then M^k(v)=r^k*v. That means if you write the column vector (1,0) as a combination of the two eigenvectors, the first entry of M^k((1,0)) must be F_k=C*((1+sqrt(5))/2)^k+D*((1-sqrt(5))/2)^k. Find the constants C and D by requiring the F_0=0 and F_1=1.

7. Mar 30, 2010

### jspectral

Okay so the Eigenvectors for mine are:

$$v_1 = \left(\frac{1 + \sqrt{5}}{2}\ , 1 \right)$$
and
$$v_2 = \left(\frac{1 - \sqrt{5}}{2}\ , 1 \right)$$

So $$A^k(v_1) = \left(\frac{1 + \sqrt{5}}{2}\ , 1 \right) \frac{1 + \sqrt{5}}{2}\$$ to the power of k for the non-vector
and
$$A^k(v_2) = \left(\frac{1 - \sqrt{5}}{2}\ , 1 \right) \frac{1 - \sqrt{5}}{2}\$$ to the power of k for the non-vector

I'm not sure what you mean to do next, how exactly do I go about writing (1,0) as a combination of $$A^k(v_1)$$ and $$A^k(v_2)$$ ?

Last edited: Mar 30, 2010
8. Mar 30, 2010

### Dick

You write it a combination of v1 and v2. Write a*v1+b*v2=(1,0) and solve for a and b. Then find what is A^k(1,0).