Power summation of $n^3$ or higher [duplicate]

Solution 1:

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.

Solution 2:

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

Solution 3:

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

Solution 4:

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)