Hi everyone!
As everybody knows, it is true 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 positive 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
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
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}$$$.
