20
$\begingroup$

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.

  • 4
    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.2011-09-12

2 Answers 2

19

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.

  • 2
    Yes, you can do so. $A$ctually, the general formula is known and goes by the name [Faulhaber formula](http://en.wikipedia.org/wiki/Faulhaber%27s_formula). I am sure if you do either Mike's approach or this approach carefully, then you should be able to derive the formula.2011-09-13
24

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

  • 1
    @Thijs: Glad it was helpful!2011-09-13