Results 1 to 5 of 5

Thread: HELP with Particular solution in the non-homogeneous recurrence relation

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    14

    HELP with Particular solution in the non-homogeneous recurrence relation

    Find the solution of the recurrence relation $\displaystyle a_{n} = 2a_{n-1} + 2n^2 $ with initial condition a1 = 4.

    As this is the linear non-homogeneous recurrence relation which has a general solution in the form of an = h(n) + p(n).

    I tried solving the h(n), homogeneous part first $\displaystyle a_{n} = 2a_{n-1} $.

    I got $\displaystyle h(n) = A2^n $ , for some constant A.

    But now i am confused about the particular solution p(n), how do i find that? Someone please help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, sanorita_belle!

    Find the solution of the recurrence relation: .$\displaystyle a_n \:=\: 2a_{n-1} + 2n^2$
    with initial condition $\displaystyle a_1 = 4$

    This is a linear non-homogeneous recurrence which has a general solution
    of the form: .$\displaystyle a_n \:=\: h(n) + p(n)$

    I tried solving the $\displaystyle h(n)$, homogeneous part first: .$\displaystyle a_n \:=\: 2a_{n-1} $

    I got: .$\displaystyle h(n) = A\!\cdot\!2^n $, for some constant $\displaystyle A.$ . . . . Good!

    But now i am confused about the particular solution $\displaystyle p(n).$
    How do i find that?
    I don't know the procedure you were taught, but I can guess . . .

    You might conjecture that the particular solution is a quadratic ...
    . . of the form: .$\displaystyle p(n) \:=\:Bn^2 + Cn + D$


    I was taught a different approach . . . quite long and tedious . . .

    . . and came up with: .$\displaystyle {\color{blue}a_n \;=\;13\!\cdot\!2^n - 2(n^2 + 4n + 6)}$

    . . which cranks out the first few terms: .$\displaystyle 4,\: 16,\: 50,\: 132,\; \hdots$

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    14
    Thanks Soroban, Can you please provide the way you learned it? It would be a great help!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, sanorita_belle!

    For the sake of anyone looking on, here it is.

    I warned you that this long and tedious . . .


    Find the solution of the recurrence relation: .$\displaystyle a_n \:=\: 2a_{n-1} + 2n^2,\;\;a_1 = 4$
    We can reduce this to a homogeneous relation ... eventually.


    $\displaystyle \begin{array}{ccccc}
    \text{previous term:} & a_{n=1} &=& 2a_{n-2} + 2(n-1)^2 & [1] \\
    n^{th}\text{ term:} & a_n &=& 2n_{n-1} + 2n^2 & [2] \end{array}$

    Subtract [2] - [1]: .$\displaystyle a_n-a_{n-1} \:=\:2a_{n-1} - 2a_{n-2} + 2n^2 - 2(n-1)^2$


    $\displaystyle \begin{array}{cccccc}\text{We have:} &a_n - 3a_{n-1} + 2a_{n-2} &=& 4n-2 & [3] \\ \text{Next term:} & a_{n+1} - 3a_n + 2a_{n-1} &=& 4(n+1)-2 & [4] \end{array}$

    Subtract [4] - [3]: .$\displaystyle a_{n+1} - a_n - 3a_n + 3a_{n-1} + 2a_{n-1} - 2a_{n-2} \:=\:[4(n-2)-2] - (4n-2) $


    $\displaystyle \begin{array}{cccccc}\text{We have:} & a_{n+1} - 4a_n + 5a_{n-1} - 2a_{n-2} &=& 4 & [5] \\
    \text{Next term:} & a_{n+2} - 4a_{n+1} + 5a_n - 2a_{n-1} &=& 4 & [6] \end{array}$

    Subtract [6] - [5]: .$\displaystyle a_{n+2} - 5a_{n+1} + 9a_n - 7a_{n-1} + 2a_{n-2} \:=\:0 $ . . . There! .Homogeneous!


    Let $\displaystyle X^n \:=\:a_n$

    We have: .$\displaystyle X^{n+2} - 5X^{n+1} + 9X^n - 5X^{n-1} + 2X^{n-2} \:=\:0$

    Divide by $\displaystyle X^{n-2}\!:\quad X^4 - 5X^3 + 9X^2 - 7X + 2 \:=\:0$

    Lucky for us, this factors: .$\displaystyle (X-1)^3(X-2) \:=\:0$

    . . which has roots: .$\displaystyle X \;=\;1,1,1,2$


    So the function is: .$\displaystyle f(n) \;=\;A(1^n) + Bn(1^n) + Cn^2(1^n) + D(2^n) $

    . . That is: .$\displaystyle f(n) \;=\;A + Bn + Cn^2 + D\cdot2^n$ .(a)


    The first four terms of the sequence are: .$\displaystyle 4,\:16,\:50,\:132$
    . . Substitute these values into (a).

    $\displaystyle \begin{array}{ccccc}f(1) = 4 & A + B + C + 2D &=& 4 & [1] \\
    f(2) = 16 & A + 2B + 4C + 4D &=& 16 & [2] \\
    f(3) = 50 & A + 3B + 9C + 8D &=& 50 & [3] \\
    f(4) = 132 & A + 4B + 16C + 16D &=& 132 & [4] \end{array}$

    $\displaystyle \begin{array}{ccccc}\text{Subtract [2] - [1]:} & B + 3C + 2D &=& 12 & [5] \\ \text{Subtract [3] - [2]:} & B + 5C + 4D &=& 34 & [6] \\
    \text{Subtract [4] - [3]:} & B + 7C + 8D &=& 82 & [7] \end{array}$

    $\displaystyle \begin{array}{ccccc}\text{Subtract[6] - [5]:} & 2C + 2D &=& 22 & [8] \\ \text{Subtract [7] - [6]:} & 2C + 4D &=& 48 & [9] \end{array}$

    $\displaystyle \text{Subtract [9] - [8]: }\;\;2D \:=\:26 \quad\Rightarrow\quad\boxed{ D \:=\:13}$

    Back-substitute and get: .$\displaystyle \boxed{C \:=\:\text{-}2} \quad\boxed{ B \:=\:\text{-}8} \quad \boxed{A \:=\:\text{-}12}$


    Therefore: .$\displaystyle f(n) \;=\;-12 - 8n - 2n^2 + 13\!\cdot\!2^n$



    I need a nap . . .
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2009
    Posts
    14

    Thumbs up

    THANKSSSS ALOT SOROBAN for all the time you spent on this question, I really appreciate it. You are the BEST

    This makes much more sense than what i learned in-class, thanks once again
    Last edited by mr fantastic; May 4th 2009 at 12:26 AM. Reason: Merged posts
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Closed-form solution of a recurrence relation.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jul 4th 2011, 02:06 PM
  2. General solution to 3rd order recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 11th 2011, 04:41 AM
  3. general solution of a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 17th 2010, 09:55 PM
  4. Find solution to a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 20th 2009, 11:17 AM
  5. Replies: 1
    Last Post: Oct 24th 2008, 10:27 AM

Search Tags


/mathhelpforum @mathhelpforum