<s>[INST] Summation of Arithmetic-Geometric Series I've been working through my homework paper, and I've come across this question. Now I'm confident in what I have done for the most part, but I am stuck at the end. 
I have this recurrence relation, that I am supposed to solve using backward substitution.
$$
T(n) = 2T(n/2) + n + 11
$$
Where n is some power of 2, for all n>1 and T(1) = 0.
I started out by some backward substitution and eventually arrived at this:
$$
2^3T(n/2^3) + 2^2(n) + 2^2(11) + 2(n) + 2(11) + n + 11
$$
And I reasoned that the general case was:
$$
2^kT(n/2^k) + 2^{k-1}(n) + 2^{k-1}(11) + 2^{k-2}(n) + 2^{k-2}(11)...2^0(n) + 2^0(11)
$$
n is a power of two, meaning that I can resolve this further:
$$
T(n) = 2^{k-1}(n) + 2^{k-1}(11) + 2^{k-2}(n) + 2^{k-2}(11)...2^0(n) + 2^0(11)
$$
Now I know I am supposed to summate this in some way, but I really don't know how! Can you guys point me in the right direction please?
 Second attempt 
I started from the beginning again, and this is how I went. I can see my answer coming closer to yours now, but I'm just struggling with one bit.
$$
T(n) = 2T(n/2) + n + 11
$$
$$
T(n) = 2^2T(n/4) + n/2 + n + 22 + 11
$$
$$
T(n) = 2^3T(n/8) + n/4 + n/2 + n + 44 + 22 + 11
$$
Factorized the 11..
$$
T(n) = 2^3T(n/8) + n/4 + n/2 + n + 11(4 + 2 + 1)
$$
I'm struggling to get from this point to your answer. Sorry to be such a pain!
 [/INST] Well $$\sum_{j=0}^{k-1} 2^j = 2^k-1$$ since it's just a geometric sum of ratio 2.
But let's check your substitution:
$$T(2^k) = 2 T(2^{k-1}) + 2^k + 11 = 2 \left(2 T(2^{k-2}) + 2^{k-1} + 11\right) + 2^k + 11$$ or
$$2^2T(2^{k-2}) + 2\times 2^k + (2 + 1)\times 11$$
Adding another term gives
$$2^2\left(2T(2^{k-3}) + 2^{k-2} + 11\right) + 2\times 2^k + (2 + 1)\times 11$$
or
$$2^3T(2^{k-3}) + 3\times 2^k + (4 + 2 + 1)\times 11$$
Edit: Note that you accidentally substituted in $T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) + \boxed{n} + 11$. The boxed term should be $\frac{n}{2}$. Then you accidentally left out the $\boxed{2} \times 2^{k-1}$ and the $\boxed{2\times 2}\times2^{k-2}$ etc.
In general, we get
$$2^k T(1) + k 2^k + (1 + 2 + \cdots + 2^{k-1})\times 11 = k 2^k+11(2^k-1)$$
or
$$T(2^k) = (k+11)2^k-11$$
</s>