Results 1 to 5 of 5

Math Help - Solving recursive sequences

  1. #1
    Member
    Joined
    Oct 2009
    Posts
    77

    Solving recursive sequences

    So I'm reviewing for an exam, and all the review question put up by the professor is as follows:

    Solve.

    r_k = 2*r_{k-1} - r_{k-2}; r_0 = 1, r_1 = 4

    We didn't really cover this in class, and the example in the book is less than adequate, so I"m not sure what to do.

    It says that a recurrence relation of the fom

    a_k = A* a_{k-1} + B * a_{k-2}

    Is satisfied by the sequence 1, t, t^2...t^n if t^2 - At - B = 0

    For this problem A = 2 and B = 0, which would make the equation

    t^2 - 2t = 0

    t(t-2) = 0

    So the roots would be t = 0 and t = 2. So the only solution would be the sequence 1, 2, 4, 16... and 1, 0, 0, ...

    Is that correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    993
    Thanks
    244
    The sequence a_k = A* a_{k-1} + B * a_{k-2} Is satisfied by the sequence 1, t, t^2...t^n if t^2 - At - B = 0.

    Yes, as can be verified by substitution. But there could be other types of sequences that satisfy the recurrence relation. For example,

    3, 6, 12, 24, 48, ...
    0, 0, 0, 0, 0, 0, ...

    But your sequence 1, 0, 0, 0, ... doesn't satisfy the recurrence relation a_k=2a_{k-1}. Do you see why?

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Let's write the difference equation as...

    r_{k+2} - 2 r_{k+1} + r_{k} =0 (1)

    It is linear homogenous constant coefficients equation and its solutions is ...

    r_{k} = c_{1}\cdot u_{k} + c_{2}\cdot v_{k} (2)

    The characteristic equation of (1) is...

    x^{2} - 2\cdot x +1 =0 (3)

    ... and it has a single root x=1 with multeplicity two. In that case is...

    u_{k} = 1^{k} = 1

    v_{k} = k\cdot 1^{k} = k (4)

    ... so that...

    r_{k} = c_{1} + c_{2}\cdot k (5)

    The 'initial conditions' r_{0}=1 , r_{1} = 4 give c_{1} = 1 , c_{2} = 3 so that is...

    r_{k} = 1 + 3\cdot k (6)

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2010
    Posts
    993
    Thanks
    244
    Yes, chisigma's answer is correct. If you set r_k=1+3k, then the k=0 and k=1 terms are easily seen to be correct. And substituting in to the recurrence relation gives:

    r_k = 2*r_{k-1} - r_{k-2}

    1+3k = 2*(1+3(k-1)) - (1+3{k-2})

    1+3k = 2+6(k-1) - (1+3k-6)

    1+3k = 2+6k-6 - 1-3k+6=1+3k, so the recurrence equations are valid.

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,802
    Thanks
    691
    Hello, Open that Hampster!

    Solve: . r_k \:=\: 2\!\cdot\!r_{k-1} - r_{k-2},\quad r_0 = 1,\;\;r_1 = 4

    I usually crank out the first few terms . . . sometimes there's an obvious pattern.

    . . \begin{array}{ccc}r_0 &=& 1 \\ r_1 &=& 4 \\ r_2 &=& 7 \\ r_3 &=& 10 \\ r_4 &=& 13 \\ & \vdots \end{array}


    This time I lucked out: . r_n \;=\;3n + 1

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sequences by primitive recursive rules?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 31st 2010, 03:45 AM
  2. Limits of recursive sequences
    Posted in the Calculus Forum
    Replies: 4
    Last Post: January 25th 2010, 04:55 AM
  3. Recursive Formulas & Sequences
    Posted in the Calculus Forum
    Replies: 3
    Last Post: April 30th 2009, 11:17 PM
  4. Sequences and the Recursive rule
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 6th 2008, 11:35 PM
  5. recursive sequences!
    Posted in the Calculus Forum
    Replies: 13
    Last Post: January 24th 2008, 05:39 PM

Search Tags


/mathhelpforum @mathhelpforum