$$given: T(n)=T(n-1)+n^3 ; T(1)=1\\=T((n-1)-1)+(n-1)^3+n^3\\=T(n-2)+(n-1)^3+n^3\\=T((n-1)-2)+(n-1-1)^3+(n-1)^3+n^3\\=T(n-3)+(n-2)^3+(n-1)^3+n^3\\…\\=T(n-k)+(n-k-1)^3+(n-k-2)^3+⋯+n^3\\n-k=1\\k=n-1\\=T(1)+(n-1)^3+(n-2)^3+⋯+n^3$$

I'm stuck here, does this look right/what would then next step be?

• It looks like you're done, as soon as you recognize what that last line means. Hint: reorder the terms so they're increasing in size. Apr 10, 2015 at 18:24
• I'm not sure what the last line means? How would I put it in terms of a summation sequence to get rid of the ...? Apr 10, 2015 at 18:32
• Do you see how the second through second to last terms are $(n - 1)^3, (n-2)^3,$ etc? For a fixed $n$, the second through second to last terms are in decreasing order -- each term is smaller than the last. Put them in increasing order. Since $T(1) = 1$, the sum is $1^3 + (n- (n - 2))^3 + (n - (n - 3))^3 + \cdots + n^3$. Simplify this expression and stare at it. Apr 10, 2015 at 19:15
• that would be $1^3+2^3+...+n^3$...then what? Apr 10, 2015 at 19:26
• Stare at it until you think of the answer. Apr 10, 2015 at 19:33

So, we have $$T(n)=\sum_{i=1}^n i^3=\left (\frac {n(n+1)}{2}\right)^2$$. The last equality is well-known and can be easily proved by induction. The base of the induction is straightforward and the step of the induction is
$$\left (\frac {n(n+1)}{2}\right)^2+(n+1)^3=\left (\frac {(n+1)(n+2)}{2}\right)^2$$
$$\frac {n^2}{4}+(n+1)= \frac {(n+2)^2}{4}$$
$$n^2+4(n+1)=(n+2)^2.$$