## Sums of powers

When you’re studying algorithms, there is a number of series and expression that keep showing up. A while ago, I discussed the special form $\sum_{i=1}^n i a^i$. But that’s not the only one. Another form that keeps showing up is

$\displaystyle s_k(n)=\sum_{i=1}^n i^k$.

We can look the particular form this sum takes for specific $k$ in some compendium (like CRC’s tables and formulae, that have seen 30-something editions over the last half century), or… you can find the formula yourself. It’s a bit tedious, but not that complicated.

Let’s pretend you don’t already know that

$\displaystyle \sum_{i=1}^ni=\frac{1}{2}n(n+1)$.

How do we get to that identity (while minimizing tears)? Legend has it that Gauss, while a kid remarked that if you write $1+2+3+\cdots+n$ on one line and $n+(n-1)+\cdots+2+1$ under, each column has sum $n+1$, that there are $n$ columns, and that the total is $n(n+1)$, but since it’s twice the sum, you need to divide by two, and you get the formula $\frac{1}{2}n(n+1)$.

But what about other powers? Say, $1^3+2^3+3^3+\cdots+n^3$? Gauss’ trick won’t work, but that doesn’t mean we’re done for. Let’s say we are interested in the sums of squares.

For the sum of squares, we will use the basic identity

$(a+1)^3-a^3=3a^2+3a+1$,

and we will use the $3a^2$ term to get the wanted expression. We write, one under the other, $n+1$ equations, starting at $a=0$ up, to $n$:

$1^3-0^3=3\cdot{}0^2+2\cdot{}0+1$

$2^3-1^3=3\cdot{}1^2+2\cdot{}1+1$

$3^3-2^3=3\cdot{}2^2+2\cdot{}2+1$

$\cdots$

$(n+1)^3-n^3=3\cdot{}n^2+2\cdot{}n+1$

Now, adding column by column, we get

$(n+1)^3=3(1+2^2+3^2+\cdots+n^2)+3(1+2+3+\cdots+n)+(n+1)$,

and therefore

$1+2^2+3^2+\cdots+n^2=\frac{1}{3}( (n+1)^3-\frac{3}{2}n(n+1)-(n+1))$

which simplifies to

$1+2^2+3^2+\cdots+n^2=\frac{1}{6}n(n+1)(2n+1)$,

the expected formula!

*
* *

If we repeat the procedure for different (integer) values of $k$, we will find:

• $\sum_{i=1}^n k^0 =n$
• $\sum_{i=1}^n k =\frac{1}{2}n(n+1) = \frac{1}{2}n^2+\frac{1}{2}n$
• $\sum_{i=1}^n k^2 =\frac{1}{6}n(n+1)(2n+1) = \frac{1}{6}(2n^3+3n^2+n)$
• $\sum_{i=1}^n k^3 =\frac{1}{4}n^2(n+1)^2 = \frac{1}{4}(n^4+2n^3+n^2)$
• $\sum_{i=1}^n k^4 =\frac{1}{3}n(n+1)(2n+1)(3n^2+3n-1)=\frac{1}{30}(6n^5+15n^4+10n^3-n)$
• etc.

However, in practice, I’ve never used more than $k=3$. But, you know, might as well have a general method.

*
* *

This method, that does not involve Bernoulli numbers, is found in a footnote of Piskunov’s Calcul différentiel et intégral, a Russian classic translated to french (and English, although I do not have an English version) by the Éditions MIR.