0
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – nomen
    Apr 10, 2015 at 18:24
  • $\begingroup$ 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 ...? $\endgroup$
    – dms94
    Apr 10, 2015 at 18:32
  • $\begingroup$ 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. $\endgroup$
    – nomen
    Apr 10, 2015 at 19:15
  • $\begingroup$ that would be $1^3+2^3+...+n^3$...then what? $\endgroup$
    – dms94
    Apr 10, 2015 at 19:26
  • $\begingroup$ Stare at it until you think of the answer. $\endgroup$
    – nomen
    Apr 10, 2015 at 19:33

1 Answer 1

1
$\begingroup$

To make the question answered.

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .