# Need help solving recurrence formula

• Sep 5th 2009, 01:25 PM
kalel918
Need help solving recurrence formula (STILL UNSOLVED)
$
T(n) = 2T(n/2) + 2
$

$
T(2) = 2
$

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

Repeat substitution...

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

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

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

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

$
= 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)
• Sep 7th 2009, 09:25 AM
kalel918
bump... anyone got any ideas? :(
• Sep 7th 2009, 12:08 PM
aidan
Quote:

Originally Posted by kalel918
$
T(n) = 2T(n/2) + 2
$

$
T(2) = 2
$

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?