Results 1 to 7 of 7

Math Help - Recurrence Relations

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    6

    Recurrence Relations

    I have been working on this problem but I cant find anything similar in my book. Not sure how to setup this problem.

    Solve the following recurrence relations together with the initial conditions given. a_n=2a_{n-1}+3a_{n-2} for n\ge 2, a_0=1, a_1=7. Thanks in advance for the help.
    Last edited by Plato; May 28th 2009 at 02:41 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    We have a_{n+2} = 2a_{n+1} + 3a_n =>  a_{n+2} - 2a_{n+1} - 3a_n = 0

    Now set a_n = w^n so we now have...

    w^{n+2} - 2w^{n+1} - 3w^{n} = 0

    w^2 - 2w - 3 = 0

    Then solve for w and we get w=3 and w=-1.

    Then put this into the general equation u_n = c_1 \cdot 3^n + c_2 \cdot (-1)^n.
    Then use your initial conditions to find the constants.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    6
    I don't really understand what you have done. I have been reading this book and still dont get it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,794
    Thanks
    1689
    Awards
    1
    Quote Originally Posted by alexriverajr View Post
    I don't really understand what you have done. I have been reading this book and still don’t get it.
    And you will not never ‘get it’ until you practice on many of these.
    So, use what you were given and solve for c_1~\&~c_2 .
    Then use that example and do several more.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Deadstar View Post
    We have a_{n+2} = 2a_{n+1} + 3a_n =>  a_{n+2} - 2a_{n+1} - 3a_n = 0 (1)

    Now set a_n = w^n so we now have...

    w^{n+2} - 2w^{n+1} - 3w^{n} = 0

    w^2 - 2w - 3 = 0

    Then solve for w and we get w=3 and w=-1. (2)

    Then put this into the general equation a_n = c_1 \cdot 3^n + c_2 \cdot (-1)^n. (3)
    Then use your initial conditions to find the constants. (4)
    (1) Since a_{n} = 2a_{n-1} + 3a_{n-2} then
    a_{n+2} = 2a_{n+1} + 3a_{n} since i doesnt matter whether we have n, n+2 or n+145334544 the relation is still the same...
    In general, a_{n+k} = 2a_{n+(k-1)} + 3a_{n+(k-2)}

    (2) Just solve the polynomial for w.

    (3) The general equation is a_n = c_1 \cdot w_1^n + c_2 \cdot w_2^n with the w terms being what you found in (2) and the c terms are constants you can find if you have initial conditions.

    (4) The initial conditions state that a_0 = 1 and a_1 = 7, This means that when n=0, a_n = 1, hence if you sub this into the equation found in (3), you get that 1 = c_1 \cdot 3^0 + c_2 \cdot (-1)^0 = c_1 + c_2
    Then sub the other initial condition in... 7 = c_1 \cdot 3^1 + c_2 \cdot (-1)^1... Solve this and you'll get two equations containing c_1 and c_2. You should be able to find the c's from there and then you have the general solution.

    I also just noticed that i had u_n in my first post instead of a_n, maybe that confused you?

    To test yourself look up gamblers ruin and try to solve it. Its similar to this.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by alexriverajr View Post
    I have been working on this problem but I cant find anything similar in my book. Not sure how to setup this problem.

    Solve the following recurrence relations together with the initial conditions given. a_n=2a_{n-1}+3a_{n-2} for n\ge 2, a_0=1, a_1=7. Thanks in advance for the help.
    Or you could use generating functions. Let  F(x) = \sum_{n \geq 0} a_{n}x^n  = a_0+a_{1}x+a_{2}x^2+a_{3}x^{3} + \cdots . Now multiply the LHS and RHS of the recurrence relation by  x^n and sum over  n . We get  \sum_{n \geq 2} a_{n}x^{n} = 2 \sum_{n \geq 2} a_{n-1}x^{n} + 3 \sum_{n \geq 2} a_{n-2}x^n . Now the key idea is to represent this by  F(x) . So  a_{2}x^{2}+a_{3}x^{3} + \cdots = 2(a_{1}x^{2}+a_{2}x^{3}+a_{3}x^2 + \cdots )+3(a_{1}x^3+a_{2}x^{4} + \cdots) . Thus  F(x)-1-7x  = 2xF(x)-2x+3x^{2}F(x)-3x^{2}.

    Now solve for  F(x) . We get  F(x)-7x = 2xF(x)-2x+3x^{2}F(x)-3x^{2}+1 . So  F(x)-2xF(x)-3x^{2}F(x) = -3x^{2}+5x+1 . Or  F(x)(1-2x-3x^2) = -3x^2+5x+1 . Thus  F(x) = \frac{-3x^2+5x+1}{1-2x-3x^2} .
    Last edited by Sampras; June 6th 2009 at 10:15 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2009
    Posts
    6
    Thanks all. Your help is really appreciated.
    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
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 24th 2011, 09:45 AM
  3. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2010, 06:59 AM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 10th 2008, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum