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 =)
 A: Observe $\sum_{k=1}^{n}kn = n\sum_{k=1}^{n}k$. Then notice the following trick: let $S = \sum_{k=1}^{n}k$. Then
$$S = 1 + 2 + \cdots + n$$
but also
$$S = n + (n-1) + \cdots + 1\text{.}$$
Convince yourself that if we add the two equations above term by term, we have
$$S + S = 2S = \underbrace{(n+1) + (n+1) + \cdots + (n+1)}_{n \text{ times}} = (n+1)n$$
hence
$$S = \dfrac{(n+1)n}{2} = O(n^2)$$
therefore what can we say about $\sum_{k=1}^{n}kn = n \sum_{k=1}^{n}k= nS$?
A: Note that $n+2n+3n+\cdots+n^2=n(1+2+3+\cdots+n)$
Do you know a formula for the sum of the first $n$ naturals?
A: We just need to understand $\sum_{k=1}^n k$.
The following is a common trick:
Think about how rectangles of width $1$ are used to approximate integrals.
If you draw this on a graph, you will soon realise that
$\int_0 ^{n-1} x\; \text{d}x<\sum_{k=1}^n k<\int_1 ^n x\; \text{d}x$.
This is the same as saying
$\frac{(n-1)^2}{2}< \sum_{k=1}^n k<\frac{n^2-1}{2}$.
$\\$
As an exercise, perhaps you might want to see if you can apply this to $\sum_{k=1}^n k^s$, for any positive $s$.
A: 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).$
