Sequence analysis of the Fibonacci sequence using matrices?

[jspectral]

Homework Statement

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

Homework Equations

See above.

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.

 

[Dick]

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

 

[jspectral]

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

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

 

[Dick]

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

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.

 

[jspectral]

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.

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

 

[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.

 

[jspectral]

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.

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

 

[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).