Need help solving recurrence formula (STILL UNSOLVED)
 = 2T(n/2) + 2<br />
)
 = 2<br />
)
Here is what I have and where I am stuck...
Repeat substitution...
![<br />
= 2[2T(n/2^2) + 2] + 2<br />](http://latex.codecogs.com/png.latex?<br />
= 2[2T(n/2^2) + 2] + 2<br />
)
 + 2^2 + 2<br />
)
![<br />
= 2^2[2T(n/2^3) + 2] + 2^2 + 2<br />](http://latex.codecogs.com/png.latex?<br />
= 2^2[2T(n/2^3) + 2] + 2^2 + 2<br />
)
 + 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)
