# 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 quick estimate. The summation is lower bounded by $\int_0^n x^k \approx \frac{n^{k+1}}{k+1}$ and upper bounded by $$\int_1^{n+1} x^k \approx \frac{(n+1)^{k+1}}{k+1} \approx \frac{n^{k+1}}{k+1} + n^{k}$$ ignoring lower order terms. (Handwaving from now on.) I would guess applying the trapezoidal rule should get you near the average, which is what you want. –  Srivatsan Sep 12 '11 at 20:54

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.

-
Thanks, this is a nice and clean solution. It looks so simple now :) –  TMM Sep 12 '11 at 23:46
Ok let me change that to just the following then: Writing out those binomials you get $$(n+1)^{k+1}=1+\sum_{i=0}^n \binom{k+1}{i} S_i(n)$$ so by isolating $S_k(n)$ you get $$S_k(n)=\frac{1}{k+1}\left((n+1)^{k+1}-1-\sum_{i=0}^{k-1} \binom{k+1}{i} S_i(n)\right)$$ –  TMM Sep 13 '11 at 1:41
Yes, you can do so. Actually, the general formula is known and goes by the name Faulhaber formula. I am sure if you do either Mike's approach or this approach carefully, then you should be able to derive the formula. –  Srivatsan Sep 13 '11 at 1:42

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

-
Thanks. I'm not too familiar with the Euler-Maclaurin formula, but obviously I should be. By the way, did you omit an error term here? –  TMM Sep 12 '11 at 23:44
I'm a huge fan of Euler-Maclaurin. I find it fascinating that it even exists and have used it in more than one research paper and several answers on math.SE. I'm a little surprised that it's not more well-known. As far as the error term, are you talking about the $O(n^{k-2})$? Since (except for $B_1$) the odd Bernoulli numbers are $0$ the even-numbered derivatives vanish from the series. –  Mike Spivey Sep 12 '11 at 23:50
I'm not surprised you're a big fan, if it allows you to turn summations into integrals so easily :) Unfortunately I do not recall ever seeing this in my studies, which is a shame. About the error term: I meant the "$+ R$" on the Wikipedia-page you linked to. I suppose you can show it is small and disappears in the $O(\cdot)$. –  TMM Sep 13 '11 at 0:00
In fact, Euler MacLaurin can be used to derive Faulhaber's formula exactly. –  Ragib Zaman Sep 13 '11 at 0:01
@Thijs: Actually, I was using the infinite series version of the formula, which is given here, although they have an asymptotic $\sim$ instead of the $=$ that holds when the series actually converges. And it does converge in this example (as I mention in my answer), since the $k+1$ derivative of $x^k$ is $0$. Euler-Maclaurin is kind of like a Taylor series: There's an infinite series version of the formula that holds when the series converges and a version with a remainder term. –  Mike Spivey Sep 13 '11 at 0:04