Results 1 to 3 of 3

Math Help - Need help solving recurrence formula

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    6

    Need help solving recurrence formula (STILL UNSOLVED)

    <br />
T(n) = 2T(n/2) + 2<br />
    <br />
T(2) = 2<br />

    Here is what I have and where I am stuck...

    Repeat substitution...

    <br />
T(n) = 2T(n/2) + 2<br />

    <br />
       = 2[2T(n/2^2) + 2] + 2<br />
    <br />
       = 2^2T(n/2^2) + 2^2 + 2<br />

    <br />
       = 2^2[2T(n/2^3) + 2] + 2^2 + 2<br />
    <br />
        = 2^3T(n/2^3) + 2^3 + 2^2 + 2<br />

    Now what? I know the base case is T(2) = 2...

    I can see the repeating pattern, but I'm not sure what to do next.

    Since k = logn (in base 2), and our base case is T(2) = 2

    would the general form be something like...
    2^(k-1) * T(n/2^[k-1]) + 2^[k-1] + 2^[k-2] + ... + 2? (i would use math tags so this looks easier but for some reason the exponents aren't coming out right with the ^ sign)
    Last edited by kalel918; September 7th 2009 at 10:26 AM. Reason: no help yet
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Aug 2009
    Posts
    6
    bump... anyone got any ideas?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by kalel918 View Post
    <br />
T(n) = 2T(n/2) + 2<br />
    <br />
T(2) = 2<br />

    Now what? I know the base case is T(2) = 2...
    and obviously,
    T(1) = 0

    There are no odd n's.
    That's odd.

    ...

     T(n) = 2 T(n/2)+2

    T(1) = 0

    T(2) = 2

    T(4) = 6

     T(8)= 14

     T(16)=30

     T(32)=62 ...
    :::
    Your numbers could be generated in sequence with this
     2^k -2

    .
    What was the question?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving a recurrence relation.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 11th 2011, 03:05 PM
  2. finding a formula for a recurrence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 8th 2010, 03:04 PM
  3. Recurrence formula
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 19th 2009, 10:21 PM
  4. recurrence formula
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 4th 2008, 10:23 AM
  5. [SOLVED] Recurrence formula
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 28th 2008, 08:21 AM

Search Tags


/mathhelpforum @mathhelpforum