# 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!

-

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

-
So is my substitution incorrect? I'm sorry, I'm really not following your explanation. –  notverygoodatmaths Apr 15 '13 at 20:15
Yes - you forgot that when you substitute in for $T(n/2)$, you get $2T(n/4) + \boxed{n/2} + 11$ –  Sharkos Apr 15 '13 at 23:10
Oh jesus of course! I'll have another look and give it another go. :) –  notverygoodatmaths Apr 15 '13 at 23:11
No worries! Sorry, I'll point it out in the answer for clarity. (I wanted to go through the whole question to make sure the technique worked easily, and there weren't any other mistakes.) –  Sharkos Apr 15 '13 at 23:13
Hi, please look at my edit. I gave it another go but I hit a bit of a stumbling block, Sorry! –  notverygoodatmaths Apr 15 '13 at 23:27