# Need help solving recurrence formula

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

Originally Posted by kalel918
\$\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?