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.

Solution 1:

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

Solution 2:

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.