Asymptotic behaviour of sums of consecutive powers Let $S_k(n)$, for $k = 0, 1, 2, \ldots$, be defined as follows
$$S_k(n) = \sum_{i=1}^n \ i^k$$
For fixed (small) $k$, you can determine a nice formula in terms of $n$ for this, which you can then prove using e.g. induction. For small $k$ we for example get
$$\begin{align}
S_0(n) &= n\\
S_1(n) &= \frac{1}{2}n^2 + \frac{1}{2}n \\
S_2(n) &= \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n \\
S_3(n) &= \frac{1}{4}n^4 + \frac{1}{2}n^3 + \frac{1}{4}n^2 \\
S_4(n) &= \frac{1}{5}n^5 + \frac{1}{2}n^4 + \frac{1}{3}n^3 - \frac{1}{30}n
\end{align}$$
The coefficients of these polynomials are related to the Bernoulli-numbers, and getting arbitrary coefficients in these polynomials (i.e. the coefficient of $n^m$ in $S_k(n)$ for large $k,m$) is not so easy. However, th first two coefficients follow a simple pattern: the coefficient of $n^{k+1}$ is $\frac{1}{k+1}$ and the coefficient of $n^k$ (for $k > 0$) is always $\frac{1}{2}$. My main question now is: 

How can we prove that $S_k(n) = \frac{1}{k+1}n^{k+1} + \frac{1}{2}n^k + O(n^{k-1})$ for $k > 0$?

The first coefficient can be explained intuitively, as
$$S_k(n) = \sum_{i=1}^n \ i^k \approx \int_{i=1}^n i^k di \approx \frac{n^{k+1}}{k+1}$$
Maybe you could make this more rigorous, but I don't see how you will get the term $\frac{1}{2}n^k$ with this.
Also, while the coefficient of $n^{k+1}$ can be explained intuitively, it's not clear to me why the coefficient of $n^k$ is $\frac{1}{2}$, and why this one is fixed while e.g. the coefficient of $n^{k-1}$ is different for different $k$. If someone could explain that, that would be appreciated as well.
Thanks.
 A: This is a classic application of the Euler-Maclaurin formula for approximating a sum by an integral.  Euler-Maclaurin says
$$\sum_{i=0}^n f(i) = \int_0^n f(x) dx + \frac{f(n)+f(0)}{2} + \sum_{i=1}^{\infty} \frac{B_{2i}}{(2i)!} \left(f^{(2i-1)}(n)-f^{(2i-1)}(0)\right),$$
where $B_i$ is the $i$th Bernoulli number.
If we take $f(x) = x^k$, the infinite series is actually finite.  The first two terms plus the first two terms from the series give us, for $k \geq 2$, $$\sum_{i=0}^n i^k = \int_0^n x^k dx + \frac{n^k}{2} + \frac{B_2}{2}k n^{k-1} + O(n^{k-3}) = \frac{n^{k+1}}{k+1} + \frac{n^k}{2} + \frac{k n^{k-1}}{12} +  O(n^{k-3}),$$
which is what you're asking for.
And, of course, if you want a better asymptotic approximation you can just take more terms from the series.
This also explains why the $n^k$ term is the only one whose coefficient does not change; it's the only one in the formula in which the function $f(x) = x^k$ rather than its integral or one of its derivatives is being evaluated at $n$.  
A: The standard way to sum $\sum\limits_{r=1}^n r^k$ gets this estimate.
We have:
$$
(r+1)^{k+1} - r^{k+1} = (k+1) r^{k} + \frac{k(k+1)}{2} r^{k-1} + O(r^{k-2}).
$$
Summing this equation for $r = 0, 1, 2, \ldots, n$, we get:
$$
(n+1)^{k+1} + O(1) = (k+1) \sum_{r=0}^nr^{k} + \frac{k(k+1)}{2} \sum_{r=0}^n r^{k-1} + \sum_{r=0}^nO(r^{k-2}).
$$
Using the inductive hypothesis that $\sum_{r=0}^n r^j = \frac{n^{j+1}}{j+1} + \frac{n^j}{2}$
for $j < k$, we get:
$$
\begin{eqnarray*}
(k+1) \sum_{r=0}^nr^{k} &=& (n+1)^{k+1} + O(1) - \frac{k(k+1)}{2} \left(\frac{n^k}{k} + \frac{n^{k-1}}{2} \right)+ \sum_{r=0}^nO(r^{k-2}).
\\ &\stackrel{(1)}{=}& \left[ n^{k+1} + (k+1)n^{k} + O(n^{k-1}) \right] + O(1) - \frac{(k+1)n^k}{2}  + O(n^{k-1})+ O(r^{k-1})
\\ &=& n^{k+1} + \frac{k+1}{2} n^k  + O(n^{k-1}),
\end{eqnarray*}
$$
where $(1)$ follows from the binomial theorem. This is equivalent to the claim.
