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