Possible Duplicate:
why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

If I want to find the formula for $$\sum_{k=1}^n k^2$$ I would do the next: $$(n+1)^2 = a(n+1)^3 + b(n+1)^2 + c(n+1) - an^3 - bn^2 - cn$$ After calculations I will match the coefficients. What equation should I use, if I want to calculate the coefficients of the formula that gives the sum $$\sum_{k=1}^n k^3$$ or higher?

EDIT: Please do not refer me to other places, not trying to blaim, or to be rude, but I find your sources too complicated for me, and unable to learn from, for my level.

If you can please explain how am I supposed to find an equation that matches to my needs, not the equation itself, only the technique I should be working with.

Regards, Guy

  • $\begingroup$ As far as I know, there is not a general and nice method of figuring this out. I attempted to learn Discrete Calculus and apply some techniques from that. Discrete Calculus is rather murky and hard to understand (for me). However, that is the one way to derive some of these formulae (from what I understand). $\endgroup$ – 000 Apr 14 '12 at 19:52

I think I know what strategy was used for the proof you are referring to for sum of squares. The same idea works for sum of cubes, but is more painful. We try to find numbers $a$, $b$, $c$, and $d$ such that $$(n+1)^3=[a(n+1)^4 +b(n+1)^3+c(n+1)^2+d(n+1)]-[an^4+bn^3+cn^2+dn].$$ To find these numbers, there are some shortcuts. But ultimately you will probably need to compute $(n+1)^2$ (familiar), $(n+1)^3=n^3+3n^2+3n+1$, and $(n+1)^4=n^4+4n^3+6n^2+4n+1$.

We get a system of $4$ equations in $4$ unknowns, but the solution turns out to be surprisingly uncomplicated. To give a start, on the left the coefficient of $n^3$ is $1$. On the right it is $4a$, so $a=\frac{1}{4}$. As a further check when you do the work, it should turn out that $d=0$.

After you have found the remaining constants $b$ and $c$, do the "collapsing" or "telescoping" argument that you seem to have seen for $\sum_{k=1}^n k^2$.


In Concrete Mathematics, there are a few methods described:

$$\begin{array}{cc} M_0 & \text{Look it up}\\ M_1 & \text{Guess the answer, prove it by induction}\\ M_2 & \text{Perturb the sum}\\ M_3 & \text{Build a repertoire}\\ M_4 & \text{Replace sums by integrals}\\ M_5 & \text{Expand and contract}\\ M_6 & \text{Use finite calculus}\\ M_7 & \text{Use generating functions} \end{array}$$

I'll describe the few that I understand. $M_0$ simply refers to the fact that all of these sums have a value set down in some sort of database (e.g. Wolfram Alpha). This is not really a satisfying answer, given that there is a clear mathematical curiosity on how these answers arise.

$M_1$ is also unsatisfying. It relies on you already knowing or happening upon the answer without any rigor or strategy.

$M_2$ is finally a somewhat satisfying method. From what I understand, you create an equation in the sum and solve that equation. Let me attempt to show you:

$$ \begin{align} \text{Let } s(n)&=\sum_{k=1}^{n}k^3\\ s(n)+(n+1)^3&=\sum_{k=0}^{n}(k+1)^3\\ &=\sum_{k=0}^{n}(k^3+3k^2+3k+1)\\ &=s(n)+3\sum_{k=0}^{n}k^2+3\sum_{k=0}^{n}k+\sum_{k=0}^{n}1 \end{align} $$

As you can see, this unfortunately fails. The point is to get your sum equated to an expression that does not involve the sum itself. Since the sum appears on both sides (with the same coefficient), you cannot solve for the sum in terms of other things.

Perturbion method (extended version) suggests doing the same thing, except you are pretending to solve for a sum that is a power higher than what you want. In other words, this:

$$ \begin{align} \text{Let } s'(n)&=\sum_{k=1}^{n}k^4\\ s'(n)+(n+1)^4&=\sum_{k=0}^{n}(k+1)^4\\ &=\sum_{k=0}^{n}k^4+4k^3+6k^2+4k+1\\ &=s'(n)+4s(n)+6\sum_{k=0}^{n}k^2+4\sum_{k=0}^{n}k+\sum_{k=0}^{n}1\\ s'(n)+(n+1)^4&=s'(n)+4s(n)+6\sum_{k=0}^{n}k^2+4\sum_{k=0}^{n}k+\sum_{k=0}^{n}1\\ \Rightarrow s(n)&=\frac{1}{4}\left((n+1)^4-6\sum_{k=0}^{n}k^2- 4\sum_{k=0}^{n}k-\sum_{k=0}^{n}1\right) \end{align} $$

The extended method, in this case, works. However, it presupposes that you know the expressions for the sums of the lower powers (in this case, the square and the natural numbers). That seems to be the only disadvantage here, so you may like this method. (If so, derive the rest of it from what I left there. :))

$M_3$ confuses me heavily because I don't fully understand Graham's recurrences nor how to use them. As such, I guess I'll leave you to look at that one should you find a copy of Concrete Mathematics.

$M_4$ relies on the fact that,

$$\int_{0}^{n}x^p dx \approx \sum_{k=1}^{n}k^p$$

Graham then suggests making the following clever realization (I take no credit for this):

$$\sum_{k=1}^{n}k^p=\int_{0}^{n}x^p dx + E(n)$$

Here $E(n)$ denotes the error term as a function of $n$. By relying on the nature of integrals and a little bit of Riemannian intuition, it can be seen that:

$$E(n)=\sum_{k=1}^{n}\left(k^p-\int_{k-1}^{k}x^p dx\right)$$

It's hard to translate this to English language (for me), so I will let you try to understand it. (It helps to apply this to lower dimensions such as 2.)

I'll apply what I just talked about right now:

$$\begin{align} \sum_{k=1}^{n}k^3&=\int_{0}^{n}x^3 dx+E(n)\\ &=\left(\frac{1}{4}x^{4}+C\right)_{0}^{n}+E(n)\\ &=\frac{1}{4}n^4+E(n)\\ E(n)&=\sum_{k=1}^{n}\left(k^3-\int_{k-1}^{k}x^3 dx\right)\\ &=\sum_{k=1}^{n}\left(k^3-\left(\frac{1}{4}x^4+C\right)_{k-1}^{k}\right)\\ &=\sum_{k=1}^{n}\left(k^3-\frac{k^4-(k-1)^4}{4}\right)\\ &=\sum_{k=1}^{n}\left(k^3-\frac{k^4-(k^4-4k^3+6k^2-4k+1)}{4}\right)\\ &=\sum_{k=1}^{n}\left(-\frac{3}{2}k^2-k-\frac{1}{4}\right) \end{align} $$

Presuming you know the expressions for the square and natural number sums, your answer becomes an algebraic exercise.

$M_5$ (mainly because of Graham's notation), $M_6$ (I don't understand finite calculus), and $M_7$ confuse me. I'll keep them listed, so that you have something to do if you decide these methods aren't satisfying.


There is a formula for this problem known as Faulhabers Formula. Specifically for the case $k = 3$, there are some easy proofs.


I have an elementary (but longer) treatize on this, but another one, which I found recently, is on 2 pages and should match your request for an elementary description, how to do that problem in general. (Peter M Lee, power sums)


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