True or false: $n^2 + 2n^2 + 3n^2 + 4n^2 + ... n(n^2)$ is $O(n^2)$

Question

I believe it is false, but having trouble coming up with the contradiction. My solution so far:

Suppose by contradiction $n^2 + 2n^2 + 3n^2 + 4n^2 + ... n(n^2)$ is $O(n^2)$, then there exists c > 0 and $n_0 \ge 1$ such that $n^2 + 2n^2 + 3n^2 + 4n^2 + ... n(n^2) < c n^2$

$n^2 + 2n^2 + 3n^2 + 4n^2 + 5n^2 ... n(n^2) = n^2(1 + 2 + 3 + 4 .. + n) \le cn^2$

$n^2\sum_{i=1}^n i = n^2(n(n+1)/2) \le cn^2$

$(n(n+1)/2) \le c$

$n^2 + n \le 2c $

Not sure where to go from here!

Answer 1

You have reached the point of $n^2+n \le 2C$ for a constant $C$ which is not possible because $n^2+n$ grows without bound.

Thus your proof is complete.

Answer 2

The last term in your sum is $n^3$, which is not $O(n^2)$. Adding positive numbers cannot reduce the order so you could be done here. In fact the whole sum is $\frac 12n(n+1)n^2=\frac 12(n^4+n^3)$ so it is $O(n^4)$