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.
