<s>[INST] 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.
 [/INST] 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$.  
</s>