Results 1 to 5 of 5

Math Help - 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  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  a_{n} = 2a_{n-1} .

    I got 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
    11,685
    Thanks
    616
    Hello, sanorita_belle!

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

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

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

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

    But now i am confused about the particular solution 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: . p(n) \:=\:Bn^2 + Cn + D


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

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

    . . which cranks out the first few terms: . 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
    11,685
    Thanks
    616
    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: .  a_n \:=\: 2a_{n-1} + 2n^2,\;\;a_1 = 4
    We can reduce this to a homogeneous relation ... eventually.


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

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


    \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]: . a_{n+1} - a_n - 3a_n + 3a_{n-1} + 2a_{n-1} - 2a_{n-2} \:=\:[4(n-2)-2] - (4n-2)


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

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


    Let X^n \:=\:a_n

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

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

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

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


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

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


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

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

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

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

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

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


    Therefore: . 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: July 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: October 17th 2010, 09:55 PM
  4. Find solution to a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 20th 2009, 11:17 AM
  5. Replies: 1
    Last Post: October 24th 2008, 10:27 AM

Search Tags


/mathhelpforum @mathhelpforum