Results 1 to 5 of 5

Math Help - Linear Recurrence Relations.

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    23

    Linear Recurrence Relations.

    I have been cruising through this weeks lecture until I reached this section.
    I will not lie, I am completely, utterly, and perhaps hopelessly lost on this topic. I begin getting lost pretty much immediately.

    One example from the books states:

     a_n=a_{n-1}+2a_{n-2}

    with  a_0=2 and a_1=7

    I feel that if I had the correct procedures down I could do the work. Any help please and thanks.

    This then translates into problems of higher degree. Such as:

     a_n=6a_{n-1} - 11a_{n-2} + 6a_{n-3}

    Initial conditions  a_0=2, a_1=5, a_2=15
    Last edited by mr fantastic; July 14th 2010 at 03:50 AM. Reason: Edited title.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Nickolase View Post
    I have been cruising through this weeks lecture until I reached this section.
    I will not lie, I am completely, utterly, and perhaps hopelessly lost on this topic. I begin getting lost pretty much immediately.

    One example from the books states:

     an=an-1+2an-2

    with  a0=2 and a1=7

    I feel that if I had the correct procedures down I could do the work. Any help please and thanks.

    This then translates into problems of higher degree. Such as:

     an=6an-1 - 11an-2 + 6an-3

    Initial conditions  a0=2, a1=5, a2=15
    Your writing is decipherable but not very pleasant to read. I'm rewriting with using the underscore character (which on my keyboard is shift-hyphen where the hyphen key is to the right of 0) and braces to get subscripts.

    ~~~~~~~~~~~~~~~~~~~~

     a_n=a_{n-1}+2a_{n-2}

    with  a_0=2 and a_1=7

    I feel that if I had the correct procedures down I could do the work. Any help please and thanks.

    This then translates into problems of higher degree. Such as:

     a_n=6a_{n-1} - 11a_{n-2} + 6a_{n-3}

    Initial conditions  a_0=2, a_1=5, a_2=15

    ~~~~~~~~~~~~~~~~~~~~

    Haven't looked at the problem yet, just thought people might like to see it properly formatted.

    Edit: Hmm looks like you fixed it in the meantime..
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Nickolase View Post
     a_n=a_{n-1}+2a_{n-2}

    with  a_0=2 and a_1=7
    This could help you, I think.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,685
    Thanks
    616
    Hello, Nickolase!

    Here is one procedure for recurrence relations.
    I'll solve the second problem.


    a_n \:=\:6a_{n-1} - 11a_{n-2} + 6a_{n-3}

    Initial conditions: a_0=2, \;a_1=5,\;a_2=15

    We assume that a_n is an exponential function.
    . .
    Let X^n = a_n.

    We have: . X^n \:=\:6X^{n-1} - 11X^{n-2} + 6X^{n-3}

    . . or: . X^n - 6X^{n-1} + 11X^{n-2} - 6X^{n-3} \;=\;0


    Divide by X^{n-3}\!:\;\;X^3 - 6X^2 + 11X - 6 \;=\;0

    . . Factor: . (X-1)(X-2)(X-3) \;=\;0

    . . Hence: . X \:=\:1,\:2,\:3

    The function is of the form: . f(n) \;=\;A\!\cdot\!1^n + B\!\cdot\!2^n + C\!\cdot\!3^n


    We know the first three terms of the sequence:

    \begin{array}{ccccccccc}<br />
f(0) = 2\!: & A + B + C &=& 2 & [1] \\<br />
f(1) = 5\!: & A + 2B + 3C &=& 5 & [2] \\<br />
F(2) = 15\!: & A + 4B+ 9C &=& 15 & [3] \end{array}

    \begin{array}{cccccccc}<br />
\text{Subtract [2] - [1]:} & B + 2C &=& 3 \\<br />
\text{Subtract [3] - [2]:} & 2B + 6C &=& 10 \end{array}

    Solve this system of equations: . B = -1,\;C = 2

    Substitute into [1]: . A - 1 + 2 \:=\:2 \quad\Rightarrow\quad A \:=\:1


    Therefore, the generating function is:

    . . f(n) \;=\;1 - 2^n + 2\!\cdot\!3^n
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    23
    Quote Originally Posted by undefined View Post
    This could help you, I think.
    Thank you. But not so much. Problem is, I just really don't even know where to begin and I don't understand why. lol It is frustrating, I think if I saw it done once through, I would understand the process. Eh, that seminar is over, so I guess I just have to hope it doesn't come up again, or in too important of a role, if I can't somehow get it sorted out.

    Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 28th 2011, 02:50 PM
  2. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  3. recurrence relations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 19th 2008, 09:08 PM
  4. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 14th 2008, 06:45 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 10th 2008, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum