adamant's blog

How to sum up all natural numbers (and their non-negative powers)
By adamant, history, 21 month(s) ago, In English

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}} $$$

Moreover, it is widely known that

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

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 non-negative 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=1}^\infty \frac{t^k x^k}{k!} = \sum\limits_{t=1}^\infty e^{tx} = \frac{e^x}{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^0&+&2^0&+&3^0&+&4^0&+&\dots &=& -1/2, \\ 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} = (-1)^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}. $$$

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{xe^x}{1-e^x} = \left(\frac{1-e^x}{x}\right)^{-1}e^{-x}$$$ and the answer would be its $$$(k+1)$$$-th coefficient, divided by $$$k!$$$.

By the way, Wikipedia also mentions that $$$\frac{t}{e^t-1}$$$ is the exponential generating function for the Bernoulli numbers, which is also consistent with the results above.

  • Vote: I like it
  • +68
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +54 Vote: I do not like it

I really wanted to set a problem that goes like "hey, please compute the sum $$$1^k+2^k+3^k+\dots$$$ for the given $$$k$$$ over all natural numbers", but in few years I couldn't come up with a formulation of the problem which could've been used in a serious contest, hence it just goes to a blog ^.^'

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

I can't believe that sum of all natural numbers equals to -1/12.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    that's why you are cyan

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    This is only true if you define summation in a specific way. Here is a detailed video about that:

    https://www.youtube.com/watch?v=YuIIjLr6vUA

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      So much is true, but is there an alternative definition which is commonly used in analysis, and provides a different meaningful sequence for all natural $$$k$$$? What I mean here, is there any reason to not consider the summation methods that are consistent with Riemann zeta function as the default ones?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The zeta function is the unique analytic continuation of the sum of the -ith powers of positive integers.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sum of "all" natural numbers can't be single number. But it is so while we don't introduce "Analytic continuation" of functions.

    Analytic continuation of function is to try define functions over it's defined range. But it is OK only in calculus. While we do not live in fantasy world, sum of every natural numbers can't be negative, can't be finite!

    Mathematics use complex analysis and analytic continuation to solve advanced problems which can't be solved with other tools. So we need it. Actually, we use it every day! So, let me repeat: In real world sum of all natural numbers != -1/12.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for your reply, now i know what it means, and thanks becuase you didnt comment like Bredor

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +145 Vote: I do not like it

Infinitely many mathematicians walk into a bar. First of them orders one pint of beer, second of them orders $$$1/2$$$ pints of beer, third orders $$$1/3$$$ pints of beer, fourth orders $$$1/4$$$ pints of beer, and so on.

Bartender feels that something's off, hence he pours the first mathematician one pint of beer, the second — two pints of beer, the third — three pints of beer, and so on. Thus, not only did the sly bartender pour everyone what they ordered (and even more), but also replenish the stock of beer by $$$1/12$$$ pints.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$\zeta(1)=\infty$$$

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeah, that's why the bartender gave the $$$k$$$-th mathematician $$$k$$$ pins instead of $$$\frac{1}{k}$$$, so that it is

      $$$\zeta(-1)= -\frac{1}{12}$$$
      → Reply