Solve the recurrence relation $T(n)=2T(\frac{n}{2})+2$ when n is a power of 2

Question

When n is 1, $T(n)=0$, when n is 2, $T(n)=2$, and when n is greater than 2, $T(n)=2T(\frac{n}{2})+2$.

I am supposed to solve this exactly, not in big O notation. Since n is a power of 2, let $n=2^k$

$$T(n)=2T(\frac{n}{2})+2$$ $$T(n)=2T(\frac{n}{4})+4+2$$ $$T(n)=2T(\frac{n}{8})+4+4+2$$ $$...k times$$ $$T(n)=2T(\frac{n}{2^k})+4k+2=4k+2=4\log n+2$$ Does this make sense?

Answer 1

Hint: Use $T(2^k)=2T(2^{k-1})+2$

$$T(2^0)=0$$ $$T(2^1)=2\cdot 0+2=2$$ $$T(2^2)=2\cdot2 +2=6$$ $$T(2^3)=2\cdot 6+2=14$$ $$T(2^4)=2\cdot14+2=30$$

You should be able to spot that $T(2^k)=2^{k+1}-2$. Can you prove it?