Results 1 to 3 of 3

Thread: Need help solving recurrence formula

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    6

    Need help solving recurrence formula (STILL UNSOLVED)

    $\displaystyle
    T(n) = 2T(n/2) + 2
    $
    $\displaystyle
    T(2) = 2
    $

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

    Repeat substitution...

    $\displaystyle
    T(n) = 2T(n/2) + 2
    $

    $\displaystyle
    = 2[2T(n/2^2) + 2] + 2
    $
    $\displaystyle
    = 2^2T(n/2^2) + 2^2 + 2
    $

    $\displaystyle
    = 2^2[2T(n/2^3) + 2] + 2^2 + 2
    $
    $\displaystyle
    = 2^3T(n/2^3) + 2^3 + 2^2 + 2
    $

    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; Sep 7th 2009 at 09: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
    $\displaystyle
    T(n) = 2T(n/2) + 2
    $
    $\displaystyle
    T(2) = 2
    $

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

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

    ...

    $\displaystyle T(n) = 2 T(n/2)+2 $

    $\displaystyle T(1) = 0$

    $\displaystyle T(2) = 2 $

    $\displaystyle T(4) = 6$

    $\displaystyle T(8)= 14$

    $\displaystyle T(16)=30 $

    $\displaystyle T(32)=62 $...
    :::
    Your numbers could be generated in sequence with this
    $\displaystyle 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: Jan 11th 2011, 02:05 PM
  2. finding a formula for a recurrence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 8th 2010, 02:04 PM
  3. Recurrence formula
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Dec 19th 2009, 09:21 PM
  4. recurrence formula
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 4th 2008, 09:23 AM
  5. [SOLVED] Recurrence formula
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 28th 2008, 07:21 AM

Search Tags


/mathhelpforum @mathhelpforum