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

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

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

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.