Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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

2 Answers 2

up vote 17 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer
    
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
1  
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
1  
In fact, Euler MacLaurin can be used to derive Faulhaber's formula exactly. –  Ragib Zaman Sep 13 '11 at 0:01
2  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.