1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sequence analysis of the Fibonacci sequence using matrices?

  1. Mar 29, 2010 #1
    1. The problem statement, all variables and given/known data
    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]

    2. Relevant equations
    See above.
    3. 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.
     
  2. jcsd
  3. Mar 29, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You need to find the eigenvalues and eigenvectors of A. Then express u0 as a combination of eigenvectors.
     
  4. Mar 29, 2010 #3
    We haven't been taught eigenvalues/vectors yet. Is there any other method you can think of to do this problem?
     
  5. Mar 29, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Mar 30, 2010 #5
    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)?
     
  7. Mar 30, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Mar 30, 2010 #7
    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: Mar 30, 2010
  9. Mar 30, 2010 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Sequence analysis of the Fibonacci sequence using matrices?
  1. Fibonacci sequence (Replies: 5)

  2. Fibonacci Sequence (Replies: 8)

  3. Fibonacci Sequence (Replies: 13)

Loading...