Show that $ \sum_{k=1}^n k n = \mathrm{O}(n^3)$ Cheers, I have to show that $ \sum_{k=1}^n k n = \mathrm{O}(n^3)$. It's a fairly easy question, but I need some answers as to that I am allowed to do.
The first way to solve this is pretty easy I think, so I stated:
$$n + 2n + 3n + \cdots + n \cdot n \leq \\ n \cdot n + n \cdot n + n \cdot n + \cdots n \cdot n = n \cdot n \cdot n = n^3 $$
so we proved it one way, basically.
Now I also tried to solve it using the limits. So I tried saying something like this:
We have to prove that: $$ \lim_{n \to \infty} \frac{\sum_{k=1}^n k n}{n^3} = 0$$
Now at this point, I have a question. Is this fraction even eligible to use L'Hopital's rule, and if yes how would that be applied? I am thinking that the limit would boil down to:
$$ \lim_{n \to \infty} \frac{\sum_{k=1}^n k n}{n^3} \stackrel{\frac{\infty}{\infty}(?)}{=} \lim_{n \to \infty} \frac{\sum_{k=1}^n k}{3n^2} = 0 $$
but I don't know If I am exactly allowed to even do that.
I also tried to split them, so I'd get:
$$ \lim_{n \to \infty} \frac{n}{n^3} + \frac{2n}{n^3} + \frac{3n}{n^3} + \cdots + \frac{n^2}{n^3} = 0 + 0 + 0 + \cdots + 0 = 0$$
Would that be a correct answer as well? Thanks for any help =)

Let $f(n) = \sum_{k=1}^{n} kn$. So
$$f(n) = \sum_{k=1}^{n} kn = n\sum_{k=1}^{n}k = n(\frac{n(n+1)}{2}) = \frac{n^3+n^2}{2}.$$
Now we can choose $M = 1$ and $N = 1$ and so
$$n \ge N : |f(n)| \le n^3.$$
So $f(n) \in O(n^3).$
