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.
