Results 1 to 5 of 5

Math Help - Compute Recurrence Relation

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Miami
    Posts
    2

    Compute Recurrence Relation

    I understand how to solve recurrence relations, however when given a problem like the one below I'm not sure what I need to do.
    I've searched google but all I ever find is how to solve the recurrence relation not how to compute like the problem below. Can someone please
    explain it too me? Thank you.

    Compute T(n) for n = 2^k


    T(n) = a for n ≤ 2
    T(n) = 8T(n/2) + bn^2 for n > 2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,849
    Thanks
    680

    Re: Compute Recurrence Relation

    Hey taleman.

    First thing I recommend is to look at this in terms of k's and k+1 instead of the n's and then look at the recurrence relation in terms of T(k) and T(k+1) or T(k-1).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Miami
    Posts
    2

    Re: Compute Recurrence Relation

    Quote Originally Posted by chiro View Post
    Hey taleman.

    First thing I recommend is to look at this in terms of k's and k+1 instead of the n's and then look at the recurrence relation in terms of T(k) and T(k+1) or T(k-1).
    not sure I understand, so I should sun n for k, then k-1, then k-2 etc?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,849
    Thanks
    680

    Re: Compute Recurrence Relation

    What I mean is to get the sequence in terms of successive integer values rather than in exponential values (which it is currently in). So in other words get T(b) in terms of T(b+1) or T(b-1) or T(b+x) where x is an integer: getting it into this form allows you to look at the expansion in terms of simple integers and then once you get it in terms of T(n) for a general integer n, you can back-substitute in terms that exponential form and get it in terms of how it was given originally.

    You are given n = 2^k but this is not in integer form, so instead of looking at T(n) in terms of T(n/2), it makes more sense to look at T(b) in terms of T(b+1) or in terms of T(b+n) for some natural number n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    54

    Lightbulb Re: Compute Recurrence Relation

    Quote Originally Posted by taleman View Post
    Compute T(n) for n = 2^k
    T(n) = a for n ≤ 2
    T(n) = 8T(n/2) + bn^2 for n > 2
    T\left(2*2^k\right)=2^{2 k-2}\left[2^{k-2}a+\left(2^k-1\right)b\right]......... k=0,1,2,3,\text{...}.
    Last edited by MaxJasper; September 30th 2012 at 08:49 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 10th 2011, 06:55 AM
  2. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 29th 2011, 11:24 PM
  3. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 19th 2009, 03:57 AM
  4. Recurrence Relation
    Posted in the Algebra Forum
    Replies: 4
    Last Post: January 14th 2009, 06:15 PM
  5. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 13th 2009, 03:55 PM

Search Tags


/mathhelpforum @mathhelpforum