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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: