Does a general formula for $\sum_{r=1}^{n}r^k$ proof exist?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.