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 . But that’s not the only one. Another form that keeps showing up is
We can look the particular form this sum takes for specific 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
How do we get to that identity (while minimizing tears)? Legend has it that Gauss, while a kid remarked that if you write on one line and under, each column has sum , that there are columns, and that the total is , but since it’s twice the sum, you need to divide by two, and you get the formula .
But what about other powers? Say, ? 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
and we will use the term to get the wanted expression. We write, one under the other, equations, starting at up, to :
Now, adding column by column, we get
which simplifies to
the expected formula!
If we repeat the procedure for different (integer) values of , we will find:
However, in practice, I’ve never used more than . 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.