Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Recurrence relation

  1. May 13, 2012 #1
    [itex]x_{xn-1}= 5_{xn-1} - 6_{xn-2};for \ n≥2 \\ x_{1}=1 \\ x_{0}=0[/itex]

    prove by induction that:
    [itex]\begin{bmatrix}
    x_{n}\\ x_{n-1}
    \end{bmatrix} = \begin{bmatrix}
    5 &-6 \\
    1 & 0
    \end{bmatrix}^{n-1}\begin{bmatrix}
    1\\0
    \end{bmatrix}[/itex]
     
  2. jcsd
  3. May 13, 2012 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    welcome to pf!

    hi dragonkiller1! welcome to pf! :wink:

    show us what you've tried, and where you're stuck, and then we'll know how to help! :smile:
     
  4. May 13, 2012 #3
    I've showed the base step for n=1
    For the inductive step:
    Suppose P(k) is true for some k
    [itex]\begin{bmatrix}
    x_{k}\\ x_{k-1}
    \end{bmatrix} = \begin{bmatrix}
    5 &-6 \\
    1 & 0
    \end{bmatrix}^{k-1}\begin{bmatrix}
    1\\0
    \end{bmatrix}[/itex]
    Then for n=k+1
    [itex]\begin{bmatrix}
    x_{k+1}\\ x_{k}
    \end{bmatrix} = \begin{bmatrix}
    5 &-6 \\
    1 & 0
    \end{bmatrix}^{k}\begin{bmatrix}
    1\\0
    \end{bmatrix}[/itex]
    ?
    I'm stuck on the inductive step. >.<
     
  5. May 13, 2012 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi dragonkiller1! :smile:

    you obviously need to prove

    [itex]\begin{bmatrix}
    x_{n+1}\\ x_{n}
    \end{bmatrix} = \begin{bmatrix}
    5 &-6 \\
    1 & 0
    \end{bmatrix}\begin{bmatrix}
    x_{n}\\ x_{n-1}
    \end{bmatrix} [/itex]

    which is easier …

    the top line or the bottom line? :wink:
     
  6. May 13, 2012 #5

    sk9

    User Avatar

    pre multiply 5,-6,1,0 matrix on both the sides(to the k equation) and you will have your proof
     
  7. May 13, 2012 #6
    Oh got it. Thanks :)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook