Does a general formula for $\sum_{r=1}^{n}r^k$ proof exist? I know that these are some existing sums that are true:
$$\sum_{r=1}^{n}r = \frac{n(n+1)}{2} = \mathcal{O}(n^2)$$
$$\sum_{r=1}^{n}r^2 = \frac{n(n+1)(2n+1)}{6} = \mathcal{O}(n^3)$$
$$\sum_{r=1}^{n}r^3 = \frac{n^2(n+1)^2}{4} = \mathcal{O}(n^4)$$
I may be butchering the definition of Big O' Notation, but I believe it describes the form of the function, i.e. the highest power of $n$ in these cases.
Is there a proof for:
$$\sum_{r=1}^{n}r^k = \mathcal{O}(n^{k+1})$$
since there seems to be this pattern?
Or even better, is there a general formulae that mirrors $$\sum_{r=1}^{n}r^k$$ in terms of only $n$ and $k$?
I didn't know how to phrase the question very well on Google, so I apologise if this question has been answered many times.
 A: The general formula for a sum of $k^{th}$ powers of the first $n$ integers is Faulhaber's formula:
$$\sum_{r=1}^n r^k=\dfrac {n^{k+1}}{k+1}+\dfrac12n^k+\sum_{r=2}^k\dfrac {B_r}{r!}\dfrac {k!}{(k-r+1)!}n^{k-r+1},$$ where $B_r$ is the $r^{th}$ Bernoulli number.  This is indeed a polynomial of degree $k+1$.
A: Jensen's Inequality implies
$$\sum_{r=1}^{n} r^k \ge n \left(\frac{\sum_{r=1}^{n} i}{n}\right)^k = n\left(\frac{n+1}{2}\right)^{k}.$$
Therefore,
$$\lim_{n \to \infty}\frac{1}{n^k}\sum_{r=1}^{n} r^k = \infty.$$
Also,
$$\lim_{n \to \infty}\frac{1}{n^{k+1}}\sum_{r=1}^{n} r^k < \lim_{n \to \infty}\frac{1}{n^{k+1}}\sum_{r=1}^{n} n^k=1.$$
Consequently,
$$\sum_{r=1}^{n} r^k = \mathcal{O}(n^{k+1}).$$
A: You can obtain a series in terms of powers of $n$. 
For the first term, note that $$\frac 1 n \sum_{r=1}^n \frac {r^k}{n^k}$$ is a Riemann sum that converges towards $$\int_0^1 x^kdx=\frac 1 {k+1}$$
Therefore 
$$\sum_{r=1}^n r^k \sim \frac{n^{k+1}}{k+1}$$
You can even obtain more terms in the expansion, and they involve Bernoulli numbers.
A: Yes there is, according to https://en.wikipedia.org/wiki/Bernoulli_number#Applications_of_the_Bernoulli_numbers
$$
\displaystyle \sum_{k=1}^{n}k^m=
\frac{1}{m+1}\sum_{k=0}^m \binom{m + 1}{k} B^+_k n^{m + 1 - k} = m! \sum_{k=0}^m \frac{B^+_k n^{m + 1 - k}}{k! (m+1-k)!}
$$
where, $B_k^+$ are bernouilli numbers
$  B^+_m = \sum_{k=0}^m \sum_{v=0}^k (-1)^v \binom{k}{v} \frac{(v + 1)^m}{k + 1}$
which gives you an explicit formula
