Help with recurrence solutions

Question

We started learning recurrences and I am having trouble with some of the problems. Our professor is having us substitute in $n=2^m$ and $S(m)=T(2^m)$ then writing down equations and summing them all up. I understand the substitution part, but not how to simplify the end result.

One of the problems I am stuck on is $T(n)=2T(n/2)+n^3$ where $T(2)=c$, When I sub in $n=2^m$ and $S(m)=T(2^m)$ I get:

$S(m)=2S(m-1)+(2^m)^3$

$S(m-1)=2S(m-2)+(2^{m-1})^3$

...

$S(3)=2S(2)+(2^{3})^3$

$S(2)=2S(1)+(2^{2})^3$

$S(1)=c$

Now because there is a coefficient on the right side we have to multiply each equation by a power of 2 so we can sum them.

$S(m)=2S(m-1)+(2^m)^3$

$2*S(m-1)=2^2S(m-2)+2*(2^{m-1})^3$

...

$2^{m-3}*S(3)=2^{m-2}S(2)+2^{m-3}(2^{3})^3$

$2^{m-2}*S(2)=2^{m-1}S(1)+2^{m-2}(2^{2})^3$

$2^{m-1}S(1)=c*2^{m-1}$

So sum these and we get:

$S(m)=(2^m)^3+2*(2^{m-1})^3+2^2*(2^{m-2})^3+...+2^{m-3}(2^{3})^3+2^{m-2}(2^{2})^3+c*2^{m-1}$

And this is where I get stuck, how can I simplify this? I tried dividing by $(2^m)^3$ but that came out to a awful mess. The other two I'm having trouble with are $T(n)=16T(n/4)+n^2$ and $T(n)=7T(n/2)+n^2$ Any help would be appreciated.

Answer 1

Once you have $S(m) = 2 S(m-1) + 2^{3m}$, you can divide by $2^m$ and obtain : $$\frac{S(m)}{2^m} = \frac{S(m-1)}{2^{m-1}} + 2^{2m}$$ Thus, setting $P(m) = \frac{S(m)}{2^m}$, you should be able to find $P(m)$, then $S(m)$.