Need help solving recurrence formula

**kalel918** · September 5th 2009, 01:25 PM

$ 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)

**kalel918** · September 7th 2009, 09:25 AM

bump... anyone got any ideas?

**aidan** · September 7th 2009, 12:08 PM

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?

Thread: Need help solving recurrence formula

LinkBack

Thread Tools

Display

Need help solving recurrence formula (STILL UNSOLVED)

Similar Math Help Forum Discussions

Solving a recurrence relation.

finding a formula for a recurrence

Recurrence formula

recurrence formula

[SOLVED] Recurrence formula

Search Tags