Recently I was giving a talk at a school in London and had cause to think about sums of kth powers, because I wanted to show people the difference between unenlightening proofs and enlightening ones. (My brief was to try to give them some idea of what proofs are and why they are worth bothering about.) On the train down, I realized that there is a very simple general argument that can be used to work out formulae for sums of kth powers. After a brief look online, I haven’t found precisely this method, though I’ve found plenty of methods in the vicinity of it. It’s bound to be in the literature somewhere, so perhaps somebody can point me towards a reference. But even so, it’s worth a short post.
I’ll start with the case \(k=1\). I want to phrase a familiar argument in a way that will make it easy to generalize in the way I want to generalize it. Let \(R_2(n)\) be the rectangle consisting of all integer points \((x,y)\) such that \(1\leq x\leq n\) and \(1\leq y\leq n+1\). We can partition \(R_2(n)\) into those points for which \(x\geq y\) and those points for which \(x<y\). The number of points of the first kind is \(1 + 2 + ... + n\), since for each \(x\) we get \(x\) possibilities for \(y\). The number of points of the second kind is \(0 + 1 + ... + n\), since for each \(y\) we get \(y-1\) possibilities for \(x\). Therefore, \(2(1 + 2 + ... + n) = n(n+1)\) and we get the familiar formula.
Now let’s move to sums of squares. This time I’ll let \(R_3(n)\) be the set of points \((x,y,z)\) with \(1\leq x\leq n\), \(1\leq y\leq n+1\) and \(1\leq z\leq n+1\). We can partition \(R_3(n)\) into three sets, the first consisting of points for which \(x\) is maximal, the second of points for which \(y\) is maximal and \(x\) is not maximal, and the third of points for which \(z\) is strictly larger than both \(x\) and \(y\). The numbers of points in these sets are easily seen to be
\(1^2 + 2^2 + \dots + n^2\)
\(0.1 + 1.2 + 2.3 + \dots + n(n+1) = 1^2 + 2^2 + \dots + n^2 + 1 + 2 + \dots + n\)
and
\(1^2 + 2^2 + \dots + n^2\),
respectively. This gives us the formula
\(3(1^2 + 2^2 + \dots + n^2) = n(n+1)^2 - n(n+1)/2 = n(n+1)(n+1/2)\)
from which we get the familiar formula \(\frac 16 n(n+1)(2n+1)\) for the sum of the first \(n\) squares. Writing \(S_k(n)\) for the sum of the first \(n\) \(k\)th powers, we also get the relationship \(3S_2(n) + S_1(n) = n(n+1)^2.\)
A striking fact about power sums is that \(S_3(n) = S_1(n)^2\). One way of explaining this can be found in a rather nice animation that I came across as a result of a Google Plus post of Richard Green. Another comes from continuing with the approach here.
This time I’ll let \(R_4(n)\) be the set of points \((x,y,z,w)\) such that \(x\) and \(y\) are between 1 and n and \(z\) and \(w\) are between 1 and \(n+1\). Again I’ll partition according to which of \((x,y,z,w)\) is the largest, taking the first one that’s largest when there is a tie. That gives me four sets. Here are their sizes.
\(x\) first largest: \(1^3 + 2^3 + \dots + n^3\).
\(y\) first largest: \(0.1^2 + 1.2^2 + \dots + (n-1).n^2\).
\(z\) first largest: \(0^2.1 + 1^2.2 + \dots + n^2.(n+1)\).
\(w\) first largest: \(0^3 + 1^3 + 2^3 + \dots + n^3\).
These sizes can be written as \(S_3(n), S_3(n)-S_2(n), S_3(n)+S_2(n)\), and \(S_3(n)\). So we get \(4S_3(n) = n^2(n+1)^2\), which gives us that \(S_3(n)=S_1(n)^2\). It also gives us a kind of explanation of that fact: for \(S_1(n)\) we decompose \(R_2(n)\) into two equal pieces of size \(S_1(n)\), while for \(S_3(n)\) we decompose \(R_2(n)^2\) into four pieces that don’t quite all have size \(S_3(n)\) but the two errors cancel out.
To see that this is a partial but not total coincidence, I’m going to jump to \(S_5(n)\) now. I’ll let \(R_6(n)\) be the set of points \((u,v,w,x,y,z)\) such that \(u,v,w\) are between 1 and \(n\) and \(x,y,z\) are between 1 and \(n+1\). This time the calculations are as follows.
\(u\) first largest: \(\sum_{k=1}^n k^5=S_5(n)\).
\(v\) first largest: \(\sum_{k=1}^n (k-1)k^4 = S_5(n)-S_4(n)\).
\(w\) first largest: \(\sum_{k=1}^n (k-1)^2k^3 = S_5(n)-2S_4(n)+S_3(n)\).
\(x\) first largest: \(\sum_{k=1}^nk^3(k+1)^2=S_5(n)+2S_4(n)+S_3(n)\).
\(y\) first largest: \(\sum_{k=1}^nk^4(k+1)=S_5(n)+S_4(n)\).
\(z\) first largest: \(\sum_{k=1}^nk^5=S_5(n)\).
Adding all these up we find that \(6S_5(n)+2S_3(n)=n^3(n+1)^3\). From that we get that
\(S_5(n)=\frac 16n^3(n+1)^3-\frac 1{12}n^2(n+1)^2\)
\(=\frac 1{12}n^2(n+1)^2(2n(n+1)-1)=\frac 1{12}n^2(n+1)^2(2n^2+2n-1).\)
In general, if we use this method to calculate \(1^k+\dots+n^k\) when \(k\) is odd, then (as with other methods) we obtain a relationship between \(S_k(n)\) and earlier \(S_j(n)\). But what is nice about it is that there is a lot of cancellation: all the \(S_j(n)\) for \(j\) even make a contribution of zero.
Indeed, if \(k=2r+1\), then we have \(k+1\) sets, and their sizes are \(S_k(n)\), \(S_k(n)-S_{k-1}(n)\), \(S_k(n)-2S_{k-1}(n)+S_{k-2}(n)\), and so on down to
\(S_k(n)-\binom r1S_{k-1}(n)+\binom r2S_{k-2}(n)-\dots+(-1)^rS_{k-r}(n)\)
and then the same thing but with all minus signs in these linear combinations replaced by plus signs. Adding it all up we get a linear combination of \(S_k(n)\), \(S_{k-2}(n)\), … , \(S_{k-t}(n)\) equalling \(n^r(n+1)^r\), where \(t=r\) if \(r\) is even and \(t=r-1\) if \(r\) is odd. When \(k\) is small, we don’t have to take into account too many \(S_j(n)\), so the formulae remain quite nice for a while before they become disgusting.
Note that it is quite easy to work out the coefficients of the various \(S_{k-2j}\) in the above linear combination: they are just sums of binomial coefficients. Several other methods require one to solve simultaneous equations, though they are usually in triangular form, so not too bad.
A small remark is that the basic idea of this argument is to discretize a much easier continuous argument that shows that \(\int_0^xt^kdt=x^{k+1}/(k+1)\). That argument is to take the \((k+1)\)-dimensional cube consisting of all points \((t_1,\dots,t_{k+1})\) such that each \(t_i\) belongs to the interval \([0,x]\) and partition it into \(k+1\) pieces according to which coordinate is largest. (I call the argument geometrical because these pieces are pyramids with \(k\)-cube bases.) In the continuous case, we don’t have to worry about what happens if there is more than one largest coordinate, since that set has measure zero. Each piece has measure \(\int_0^xt^kdt\), and there are \(k\) pieces, while the cube has measure \(x^{k+1}\), so we are done.
A second remark is that the method I previously knew of for calculating sums of \(k\)th powers is to exploit the fact that deserves to be called the natural discrete analogue of the above. Define \(n_k\) to be \(n(n-1)\dots(n-k+1)\). This we think of as the discrete analogue of \(x^k\). Then we do a discrete analogue of differentiating, which is to look at \((n+1)_k-n_k\), which equals \(n(n-1)\dots(n-k+2)(n+1-(n-k+1))=kn_{k-1}\). This is the discrete analogue of the fact that the derivative of \(x^k\) is \(kx^{k-1}\). Next, we use the discrete analogue of the fundamental theorem of calculus, which is the statement that \(\sum_{i=m}^{n-1}(f(i+1)-f(i))=f(n)-f(m)\) to deduce that \(\sum_{m=1}^n km_{k-1}=n_k\). This gives us for each \(k\) a polynomial of degree \(k\) that we can sum easily, namely \(n_k\), and then to work out the sum of the first \(k\)th powers, we write it as a linear combination of the \(n_k\), sum everything, and simplify the answer. That works fine, but the calculations are quite a bit more complicated than what I did above, and the proof is too algebraic to explain why the answers have the fairly nice forms they do. (For example, why is \(n^2(n+1)^2\) a factor of the sum of the first \(n\) \(k\)th powers whenever \(k\) is odd and at least 3? From the argument I gave earlier in the post, this follows fairly easily by induction.)
This entry was posted on November 4, 2014 at 10:18 pm and is filed under Straight maths. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.