• Support PF! Buy your school textbooks, materials and every day products Here!

Sequence analysis of the Fibonacci sequence using matrices?

  • Thread starter jspectral
  • Start date
  • #1
12
0

Homework Statement


Using [tex]u_k = \[ \left( \begin{array}{ccc} F_{k+1} \\ F_k \end{array} \right)\] [/tex] [tex] u_0 = \[ \left( \begin{array}{ccc} 1 \\ 0 \end{array} \right)\][/tex] [tex] A = \[ \left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array} \right)\][/tex]
Solve for [tex]u_k[/tex] in terms of [tex]u_0[/tex] to show that:

[tex]F_k = \frac{1}{\sqrt{5}}\ \left(\left(\frac{1 + \sqrt{5}}{2}\ \right)^k - \left(\frac{1 - \sqrt{5}}{2}\ \right)^k\right) [/tex]

Homework Equations


See above.

The Attempt at a Solution


Well, I worked out that [tex]u_k = A^k u_0 [/tex]
[tex] \[ \left( \begin{array}{ccc} F_{k+1} \\ F_k \end{array} \right)\][/tex] = [tex]\[ \left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array} \right)\]^k[/tex] [tex]\[ \left( \begin{array}{ccc} 1 \\ 0 \end{array} \right)\] [/tex]

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.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
You need to find the eigenvalues and eigenvectors of A. Then express u0 as a combination of eigenvectors.
 
  • #3
12
0
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?
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #5
12
0
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 [tex]\left(\frac{1 \pm \sqrt{5}}{2}\ \right)[/tex]

Now how do I use those eigenvalues with the power of k in order to obtain an expression for F_(k)?
 
  • #6
Dick
Science Advisor
Homework Helper
26,258
618
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
12
0
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:

[tex]
v_1 = \left(\frac{1 + \sqrt{5}}{2}\ , 1 \right)
[/tex]
and
[tex]
v_2 = \left(\frac{1 - \sqrt{5}}{2}\ , 1 \right)
[/tex]

So [tex] A^k(v_1) = \left(\frac{1 + \sqrt{5}}{2}\ , 1 \right) \frac{1 + \sqrt{5}}{2}\ [/tex] to the power of k for the non-vector
and
[tex] A^k(v_2) = \left(\frac{1 - \sqrt{5}}{2}\ , 1 \right) \frac{1 - \sqrt{5}}{2}\ [/tex] 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 [tex] A^k(v_1) [/tex] and [tex] A^k(v_2) [/tex] ?
 
Last edited:
  • #8
Dick
Science Advisor
Homework Helper
26,258
618
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).
 

Related Threads for: Sequence analysis of the Fibonacci sequence using matrices?

  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
5
Views
2K
Replies
6
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
3K
Replies
16
Views
10K
Top