Results 1 to 3 of 3

Math Help - Simple recurrence relations question

  1. #1
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39

    Simple recurrence relations question

    Hello,
    I have two textbook examples of simple non-homogeneous recurrences with model solutions, but there's one thing that I don't understand in both of them.

    First recurrence: u_0=3, \ u_1=20
    u_n=4u_{n-1}-4u_{n-2}-6n+1, \ n \geq 2

    Characteristic equation ( x^2-4x+4=0) has double characteristic root 2.

    Non-homogeneous part is first degree polynomial, so the guess is p(n)=an+b. Then we substitute it to original recurrence and get following equation:
    an+b=4(a(n-1)+b)-4(a(n-2)+b)-6n+1=-6n+4a+1

    Now comes the part, that I don't understand. Textbook says, that we get two solutions ( a=-6 and b=-23) from that equation. But it completely baffles me, how I'am supposed to get those solutions. I think it have something to do with method of undetermined coefficients, but we haven't got taught anything about it, gg. Rest of the solution I understand.

    Second recurrence: a_n=a_{n-1}+a_{n-2}+2n (no other information given)

    Guess is form p(n)=bn+c. And subtitution to recurrence:
    bn+c=(b(n-1)+c)+(b(n-2)+c)+2n \Leftrightarrow -bn+(3b-c)=2n

    Now I don't understand even, how that right side of biconditional is got.
    When I reduce that equation, I get something like: 2bn-3b+2c+2n. Again equation is "solved" and b=-2 and c=-6 is got, which I don't understand at all.

    So, any help is appreciated. Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by Greg98 View Post
    Hello,
    I have two textbook examples of simple non-homogeneous recurrences with model solutions, but there's one thing that I don't understand in both of them.

    First recurrence: u_0=3, \ u_1=20
    u_n=4u_{n-1}-4u_{n-2}-6n+1, \ n \geq 2

    Characteristic equation ( x^2-4x+4=0) has double characteristic root 2.

    Non-homogeneous part is first degree polynomial, so the guess is p(n)=an+b. Then we substitute it to original recurrence and get following equation:
    an+b=4(a(n-1)+b)-4(a(n-2)+b)-6n+1=-6n+4a+1

    Now comes the part, that I don't understand. Textbook says, that we get two solutions ( a=-6 and b=-23) from that equation. But it completely baffles me, how I'am supposed to get those solutions. I think it have something to do with method of undetermined coefficients, but we haven't got taught anything about it, gg. Rest of the solution I understand.

    Second recurrence: a_n=a_{n-1}+a_{n-2}+2n (no other information given)

    Guess is form p(n)=bn+c. And subtitution to recurrence:
    bn+c=(b(n-1)+c)+(b(n-2)+c)+2n \Leftrightarrow -bn+(3b-c)=2n

    Now I don't understand even, how that right side of biconditional is got.
    When I reduce that equation, I get something like: 2bn-3b+2c+2n. Again equation is "solved" and b=-2 and c=-6 is got, which I don't understand at all.

    So, any help is appreciated. Thank you!
    Your form of the particular solution is correct.

    p(n)=an+b Now we just plug this into the equation below

    u_n-4u_{n-1}+4u_{n-2}=-6n+1 This gives

    an+b-4[a(n-1)+b]+4[a(n-2)+b]=-6n+1 Now expand the left hand side to get

    an+b-4an+4a-4b+4an-8a+4b=-6n+1 simplifying gives

    an-4a+b=-6n+1 Now for this to be true the coefficients must be equal and satisfy this system of equation

    \begin{array}{c c c } a &+0b &=-6 \\ -4a & +b & =1\end{array}

    This gives that values of a and b

    Try the 2nd one again (using what I did above) and note that this may be helpful

    a_n-a_{n-1}-a_{n-2}=2n+0
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39
    That was great clarification - just what I was looking for. This problem has been puzzling me for long, though I managed to pass the course with a decent grade. Huge thanks to you!!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Probability question involving recurrence relations
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: May 5th 2011, 01:07 PM
  2. Simple question on relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2010, 04:18 AM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  4. Replies: 3
    Last Post: February 10th 2009, 03:51 AM
  5. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 14th 2008, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum