With the help of this table it took me less than half of a quarter of an hour to find that the tenth powers of the first thousand numbers, added together, give 91,409,924,241,424,243,424,241,924,242,500.

— Jakob Bernoulli, Ars conjectandi (1713), part II

The story goes that young Gauss added the numbers from 1 to 100 in seconds, pairing the first with the last: $1+2+\cdots+n=\frac{n(n+1)}2$. For squares and cubes there are formulas too, known since Archimedes and the Arab mathematicians:

$$\begin{aligned}1^2+2^2+\cdots+n^2&=\frac{n(n+1)(2n+1)}6,\\ 1^3+2^3+\cdots+n^3&=\left(\frac{n(n+1)}2\right)^2.\end{aligned}$$

And for fourth, fifth, tenth powers? In the seventeenth century several mathematicians filled pages with these formulas, one at a time. The Frenchman Ismaël Boulliau published in 1682 a bulky book that, with great effort, only reached the sixth powers. Jakob Bernoulli found a rule that gives all of them.

The table

In the second part of the Ars conjectandi, Jakob wrote the formulas one below the other and looked at them carefully:

$$\begin{aligned}\sum_{k=1}^n k&=\tfrac12n^2+\tfrac12n\\ \sum_{k=1}^n k^2&=\tfrac13n^3+\tfrac12n^2+\tfrac16n\\ \sum_{k=1}^n k^3&=\tfrac14n^4+\tfrac12n^3+\tfrac14n^2\\ \sum_{k=1}^n k^4&=\tfrac15n^5+\tfrac12n^4+\tfrac13n^3-\tfrac1{30}n\\ \sum_{k=1}^n k^5&=\tfrac16n^6+\tfrac12n^5+\tfrac5{12}n^4-\tfrac1{12}n^2\end{aligned}$$

There is a pattern. The sum of the $m$-th powers is always a polynomial of degree $m+1$. The first coefficient is $\frac1{m+1}$, as in the integral $\int_0^n x^m\,dx=\frac{n^{m+1}}{m+1}$. The second is always $\frac12$. And the following ones look like the coefficients of the binomial $(n+1)^{m+1}$, only multiplied by certain fixed numbers.

The mysterious numbers

Jakob realised that a single list of numbers, now written $B_0,B_1,B_2,\dots$ and called Bernoulli numbers, was enough to write all the formulas at once:

$$\boxed{\sum_{k=1}^n k^m=\frac1{m+1}\sum_{j=0}^{m}\binom{m+1}{j}B_j\,n^{m+1-j}}$$

How do we find the $B_j$? There is a simple trick: the formula must hold for $n=1$, when the sum is just $1^m=1$. Putting $n=1$, all the powers of $n$ become 1, and what is left is

$$\sum_{j=0}^{m}\binom{m+1}{j}B_j=m+1.$$

Starting with $B_0=1$, each value of $m$ gives the next number:

  • $m=1$: $1+2B_1=2$, so $B_1=\frac12$.
  • $m=2$: $1+3\cdot\frac12+3B_2=3$, so $B_2=\frac16$.
  • $m=3$: $1+4\cdot\frac12+6\cdot\frac16+4B_3=4$, so $B_3=0$.
  • $m=4$: $1+5\cdot\frac12+10\cdot\frac16+0+5B_4=5$, so $B_4=-\frac1{30}$.

Going on, $B_6=\frac1{42}$, $B_8=-\frac1{30}$, $B_{10}=\frac5{66}$, and all those with an odd index greater than 1 are zero. The numbers follow no obvious pattern: $B_{12}=-\frac{691}{2730}$, and from there on they grow very quickly.

The seven minutes

With the list, the formula for tenth powers comes out directly:

$$\begin{aligned}\sum_{k=1}^n k^{10}={}&\tfrac1{11}n^{11}+\tfrac12n^{10}+\tfrac56n^9-n^7\\&+n^5-\tfrac12n^3+\tfrac5{66}n.\end{aligned}$$

For $n=1{,}000$, each term is a power of 10 times a simple fraction. The first is $\frac{10^{33}}{11}=90{,}909{,}090\ldots$, the second is $5\cdot10^{29}$, the third is $\frac{10^{27}\cdot5}6$, and so on. Adding them is a matter of lining up decimal places. Hence the jibe in the quotation: Jakob did in “half of a quarter of an hour”, about seven minutes, the calculation that Boulliau could not have done with his whole book.

Why it works

The idea behind it all is that of a difference. If $F(n)=\sum_{k=1}^n k^m$, then $F(n)-F(n-1)=n^m$. Now, if $F$ is a polynomial of degree $m+1$, the difference $F(n)-F(n-1)$ is a polynomial of degree $m$. So finding the formula means finding a polynomial whose difference is $n^m$: it is the discrete version of finding a function whose derivative is $x^m$. The Bernoulli numbers measure how far the sum strays from the integral.

This bridge between sums and integrals was developed by Euler and Maclaurin, around 1735, in a formula that bears both their names and in which the Bernoulli numbers appear in every term. In 1843, Ada Lovelace wrote an algorithm to compute the Bernoulli numbers on Charles Babbage’s Analytical Engine. It is considered the first published computer program.

Exercise: use the formula to check the sum of the fourth powers from 1 to 10.

With $m=4$: $\sum k^4=\frac15n^5+\frac12n^4+\frac13n^3-\frac1{30}n$. For $n=10$:

$$20{,}000+5{,}000+333.\overline3-0.\overline3=25{,}333.$$

Check by adding: $1+16+81+256+625+1{,}296+2{,}401+4{,}096+6{,}561+10{,}000=25{,}333$.

Exercise: why is the sum of the cubes the square of the sum of the numbers?

From the table, $\sum k^3=\frac14n^4+\frac12n^3+\frac14n^2=\frac{n^2(n^2+2n+1)}4=\frac{n^2(n+1)^2}4$, which is $\left(\frac{n(n+1)}2\right)^2$. For example, $1^3+2^3+3^3+4^3=100=(1+2+3+4)^2$. With $n=100$, the sum of the cubes is $5{,}050^2=25{,}502{,}500$.

Sources: Jakob Bernoulli, The Art of Conjecturing, part II, ch. 3, trans. Edith Dudley Sylla (Johns Hopkins, 2006) · Donald E. Knuth, “Johann Faulhaber and sums of powers”, Mathematics of Computation 61 (1993) · biography of Seki Takakazu, MacTutor.

All topics on James Bernoulli · ← The golden theorem: the law of large numbers · The legacy of James Bernoulli →

Image credits.