How to sum up all natural numbers (and their positive powers)

Revision en5, by adamant, 2023-02-28 00:53:49

Hi everyone!

This is the blog for infinite sums. For finite sums of power, see here.

As everybody knows, it is true that

$$$ \boxed{1+2+3+4+\dots = -\frac{1}{12}} $$$

Historically, it seems that the result was first discovered by Ramanujan, who described it in one of his letters to G. Hardy as

$$$ \text{"If I tell you this you will at once point out to me the lunatic asylum as my goal"} $$$

In this blog, I want to explain how this summation could be easily done with the competitive programmer's favorite tool: generating functions. Moreover, I will explain how to compute the infinite sums of form $$$1^k + 2^k + 3^k + 4^k + \dots = S_k$$$ for any positive integer $$$k$$$.

All your problems will go away with this simple genfunc trick. Just use...

Consider the exponential generating function

$$$ S(x) = \sum\limits_{k=0}^\infty \frac{S_k}{k!} x^k. $$$

Expanding $$$S_k$$$ into infinite sum, we get

$$$ \boxed{S(x) = \sum\limits_{k=0}^\infty \sum\limits_{t=0}^\infty \frac{t^k x^k}{k!} = \sum\limits_{t=0}^\infty e^{tx} = \frac{1}{1-e^{x}}} $$$

It doesn't converge at $$$x = 0$$$, where we typically analyze genfuncs, but should it bother us? The expression expands as a Laurent series

$$$ S(x) = -\frac{1}{x} + \frac{1}{2} - \frac{x}{12} + \frac{x^3}{720} - \frac{x^5}{30240} + \dots, $$$

which means that

$$$\begin{gather} 1^1&+&2^1&+&3^1&+&4^1&+&\dots &=& -1/12, \\ 1^2&+&2^2&+&3^2&+&4^2&+&\dots &=& 0, \\ 1^3&+&2^3&+&3^3&+&4^3&+&\dots &=& 1/120, \\ 1^4&+&2^4&+&3^4&+&4^4&+&\dots &=& 0, \\ 1^5&+&2^5&+&3^5&+&4^5&+&\dots &=& -1/252. \end{gather}$$$

If you do some investigation on the sequence of denominators, you'll notice that it is OEISable and is related to the so-called Bernoulli numbers. On closer inspection, you may notice that, generally,

$$$ S_{k} = -\frac{B_{k+1}}{k+1}, $$$

where $$$B_k$$$ is the $$$k$$$-th Bernoulli number. But what does it have to do with the task at hand?

A complex problem, a complex solution...

Consider another way to define the sum of powers of natural numbers, using $$$s$$$ as a parameter:

$$$ \zeta(s) = 1^{-s} + 2^{-s} + 3^{-s} + 4^{-s} + \dots $$$

The function $$$\zeta(s)$$$ converges for any $$$s > 1$$$, which, using some complex analysis magic, allows to find its unique analytic continuation on the whole complex plane $$$\mathbb C$$$, except for the point $$$s=1$$$. In other words, there is a meaningful definition of

$$$ \zeta(-k) = 1^k + 2^k + 3^k + 4^k + \dots $$$

for any integer $$$k > 0$$$. Okay then, what are the values of such function? I don't really know, but Wikipedia says that

$$$ \zeta(-k) = (-1)^k \frac{B_{k+1}}{k+1}, $$$

which is same as above, knowing that $$$B_{2k} = 0$$$. Well, that's nice to know! We have no idea about Bernoulli numbers, or any other properties of Riemann zeta functions $$$\zeta(s)$$$, yet we obtained some meaningful result with seemingly completely wrong formal manipulations. So, if we ever want to compute the infinite sum

$$$ S_k = 1^k + 2^k + 3^k + 4^k + \dots, $$$

we should just expand the formal power series $$$\frac{x}{1-e^x} = \left(\frac{1-e^x}{x}\right)^{-1}$$$ and then the answer would be its $$$(k+1)$$$-th coefficient, divided by $$$k!$$$.

Note: the formulas above only work for $$$k > 0$$$. With $$$k=0$$$ it would yield $$$\frac{1}{2}$$$, but the "correct" answer should be $$$-\frac{1}{2}$$$.

By the way, Wikipedia also mentions that $$$\frac{t}{e^t-1}$$$ is, in turn, the exponential generating function for the Bernoulli numbers.

Tags fun with genfuncs, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English adamant 2023-03-02 00:27:14 13
en11 English adamant 2023-02-28 12:59:29 49
en10 English adamant 2023-02-28 01:04:44 5
en9 English adamant 2023-02-28 01:03:33 140
en8 English adamant 2023-02-28 01:02:13 14
en7 English adamant 2023-02-28 01:01:03 29
en6 English adamant 2023-02-28 00:59:09 272
en5 English adamant 2023-02-28 00:53:49 120
en4 English adamant 2023-02-28 00:22:02 208
en3 English adamant 2023-02-28 00:19:20 18
en2 English adamant 2023-02-28 00:18:17 23
en1 English adamant 2023-02-28 00:17:05 3513 Initial revision (published)