Results 1 to 9 of 9

Math Help - non-homogneous recurrence relation

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    24

    non-homogneous recurrence relation

    Hi,

    i like to solve the attached recurrence relation, i know the homogenous solution but the problem is with the cos term.

    Help is appreciated!

    Mopen
    Attached Thumbnails Attached Thumbnails non-homogneous recurrence relation-recurrence.png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: non-homogneous recurrence relation

    The cosine is periodic so you should only need consider four cases, yes?

    What are the base cases?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    24

    Re: non-homogneous recurrence relation

    sorry, what you mean by base cases?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: non-homogneous recurrence relation

    I may be coming from a different field, but when we do recurrences in computer science, there needs to be some foundation from which the recurrence begins. It's important to consider the foundation in the event its contribution outweighs the rest of the recurrence.

    For example, if T(n) = 3T(n/2) + n, you need to know what T(c) contributes for some small constant value (usually just described as T(0) since the value is irrelevant).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2011
    Posts
    24

    Re: non-homogneous recurrence relation

    yes the recurrence starts from T(0)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: non-homogneous recurrence relation

    Okay. Well, then you should be able to expand out the recurrence until it's completely periodic...maybe...

    T(n) = 2T(n-1) - T(n-2) - (2cos(n\pi/2))/(n-1)
    T(n-1) = 2T(n-2) - T(n-3) - (2cos((n-1)\pi/2))/(n-2)
    T(n-2) = 2T(n-3) - T(n-4) - (2cos((n-2)\pi/2))/(n-3)
    T(n-3) = 2T(n-4) - T(n-5) - (2cos((n-3)\pi/2))/(n-4)

    So:

    T(n) = 4T(n-2) - T(n-2) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)

    = 3T(n-2) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)

    = 6T(n-3) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)

    = 4T(n-3) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)

    = 8T(n-4) - 4T(n-5) - (8cos((n-3)\pi/2))/(n-4) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)

    = 5T(n-4) - 4T(n-5) - (8cos((n-3)\pi/2))/(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)

    Which confirms:

    T(n) = - (2cos(n\pi/2))/(n-1) - (4cos(n-1\pi/2))/(n-2) - (6cos(n-2\pi/2))/(n-2) - ...

    ...over lg n many terms. We can reframe T(c) as T(1), after which the summation should be:

    T(n) = -2 \sum_{i=1}^{n} i(cos(n-i)\pi/2))/(n-i)

    EDIT: If we assume T(0) = 0 there's no problem but otherwise you have to add an extra 3^n * T(0) (roughly speaking) to the total for the contribution of the base case, but you didn't say what the base case contribution was. It appears to be substantial, however.

    I'm not good at simplification of series with transcendentals (too applied for my tastes) but I assume you can handle it here.

    Hope that helps!
    Last edited by Annatala; December 3rd 2011 at 11:42 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: non-homogneous recurrence relation

    Wait, I made a big error. Need to recalculate, give me a moment. I'll edit this message when finished.

    EDIT: Nevermind, we're good. (For a moment there I thought I hadn't handled signs properly but I was always adding at the beginning of the recurrence so it works.)

    EDIT 2: Although I did make an error with the cosines at the end...just fixed. I hope it's close to correct now. Either way you should see how I did it.

    EDIT 3: Sheesh. Summation should go from 1 to n, and contribution of leaves is 3^n * T(0), which is significant unless T(0) = 0. Last fix, honest.
    Last edited by Annatala; December 3rd 2011 at 11:44 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Sep 2011
    Posts
    24

    Re: non-homogneous recurrence relation

    just small modification see the first attachement X is a variable 0<X<1 also i attached T(0) and T(1) as function of X

    thank you so much
    Attached Thumbnails Attached Thumbnails non-homogneous recurrence relation-untitled2.png   non-homogneous recurrence relation-untitled1.png  
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: non-homogneous recurrence relation

    Oh! I thought that was 2 times, not 2x.

    If there's an x and an n in there, I don't know what to make of it. I guess the x is a constant and you're looking for a result that hinges on both n and x, but that's frightening.

    Recurrences in CS don't even get this crazy so it's beyond my ability to solve at present, and I don't have much interest in learning. Best of luck with it, maybe someone else can assist you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 11:27 PM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 02:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 01:18 PM
  4. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 08:02 AM
  5. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 8th 2008, 09:47 AM

Search Tags


/mathhelpforum @mathhelpforum