Hi everyone!
This is the blog for infinite sums. For finite sums of power, see here.
As everybody knows, it is true that
Moreover, it is widely known that
Historically, it seems that the result was first discovered by Ramanujan, who described it in one of his letters to G. Hardy as
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
Expanding $$$S_k$$$ into infinite sum, we get
It doesn't converge at $$$x = 0$$$, where we typically analyze genfuncs, but should it bother us? The expression expands as a Laurent series
which means that
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,
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:
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
for any integer $$$k > 0$$$. Okay then, what are the values of such function? I don't really know, but Wikipedia says that
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
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.
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 ^.^'
I can't believe that sum of all natural numbers equals to -1/12.
that's why you are cyan
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
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?
The zeta function is the unique analytic continuation of the sum of the -ith powers of positive integers.
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.
Thank you for your reply, now i know what it means, and thanks becuase you didnt comment like Bredor
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.
$$$\zeta(1)=\infty$$$
Yeah, that's why the bartender gave the $$$k$$$-th mathematician $$$k$$$ pins instead of $$$\frac{1}{k}$$$, so that it is