Results 1 to 7 of 7

Thread: 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. $\displaystyle a_n=2a_{n-1}+3a_{n-2}$ for $\displaystyle n\ge 2$, $\displaystyle 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 $\displaystyle a_{n+2} = 2a_{n+1} + 3a_n => a_{n+2} - 2a_{n+1} - 3a_n = 0$

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

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

    $\displaystyle w^2 - 2w - 3 = 0$

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

    Then put this into the general equation $\displaystyle 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
    21,796
    Thanks
    2827
    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 $\displaystyle 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 $\displaystyle a_{n+2} = 2a_{n+1} + 3a_n => a_{n+2} - 2a_{n+1} - 3a_n = 0$ (1)

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

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

    $\displaystyle 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 $\displaystyle 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 $\displaystyle a_{n} = 2a_{n-1} + 3a_{n-2}$ then
    $\displaystyle 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, $\displaystyle a_{n+k} = 2a_{n+(k-1)} + 3a_{n+(k-2)}$

    (2) Just solve the polynomial for w.

    (3) The general equation is $\displaystyle 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 $\displaystyle a_0 = 1$ and $\displaystyle a_1 = 7$, This means that when $\displaystyle n=0, a_n = 1$, hence if you sub this into the equation found in (3), you get that $\displaystyle 1 = c_1 \cdot 3^0 + c_2 \cdot (-1)^0 = c_1 + c_2$
    Then sub the other initial condition in... $\displaystyle 7 = c_1 \cdot 3^1 + c_2 \cdot (-1)^1$... Solve this and you'll get two equations containing $\displaystyle c_1$ and $\displaystyle 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 $\displaystyle u_n$ in my first post instead of $\displaystyle 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. $\displaystyle a_n=2a_{n-1}+3a_{n-2}$ for $\displaystyle n\ge 2$, $\displaystyle a_0=1, a_1=7$. Thanks in advance for the help.
    Or you could use generating functions. Let $\displaystyle 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 $\displaystyle x^n $ and sum over $\displaystyle n $. We get $\displaystyle \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 $\displaystyle F(x) $. So $\displaystyle 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 $\displaystyle F(x)-1-7x = 2xF(x)-2x+3x^{2}F(x)-3x^{2}$.

    Now solve for $\displaystyle F(x) $. We get $\displaystyle F(x)-7x = 2xF(x)-2x+3x^{2}F(x)-3x^{2}+1 $. So $\displaystyle F(x)-2xF(x)-3x^{2}F(x) = -3x^{2}+5x+1 $. Or $\displaystyle F(x)(1-2x-3x^2) = -3x^2+5x+1 $. Thus $\displaystyle F(x) = \frac{-3x^2+5x+1}{1-2x-3x^2} $.
    Last edited by Sampras; Jun 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: Jul 28th 2011, 02:50 PM
  2. Recurrence relations
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Feb 24th 2011, 09:45 AM
  3. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 1st 2010, 06:59 AM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 6th 2009, 07:56 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Feb 10th 2008, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum