Evaluating a class of infinite sums in closed form | Hacker News Reader

Evaluating a class of infinite sums in closed form

johndcook.com

160 pointsbeefman34 comments

Another way to get to the same result is to use "Feynman's Trick" of differentiating inside a sum:

Consider the function f(x) = Sum_{n=1}^\infty c^(-xn)

Then differentiate this k times. Each time you pull down a factor of n (as well as a log(c), but that's just a constant). So, the sum you're looking for is related to the kth derivative of this function.

Now, fortunately this function can be evaluated explicitly since it's just a geometric series: it's 1 / (c^x - 1) -- note that the sum starts at 1 and not 0. Then it's just a matter of calculating a bunch of derivatives of this function, keeping track of factors of log(c) etc. and then evaluating it at x = 1 at the very end. Very labor intensive, but (in my opinion) less mysterious than the approach shown here (although, of course the polylogarithm function is precisely this tower of derivatives for negative integer values).

Instead of differentiating c^(-xn) w.r.t. x to pull down factors of n (and inconvenient logarithms of c), you can use (z d/dz) z^n = n z^n to pull down factors of n with no inconvenient logarithms. Then you can set z=1/2 at the end to get the desired summand here. This approach makes it more obvious that the answer will be rational.

This is effectively what OP does, but it is phrased there in terms of properties of the Li function, which makes it seem a little more exotic than thinking just in terms of differentiating power functions.

To be honest, the whole use of the Li function before defining it made me stop reading.

Yeah, differentiating these infinite sums to pull down polynomial factors is a familiar trick.

It happens in basic moment generating function manipulations (e.g., higher moments of random variables). Or from z-transforms in signal processing (z transforms of integrals or derivatives). And (a little less obvious, but still the same) from Fourier analysis.

The concept applies to any moment generating function, z-transform, whatever. It’s clearest for the geometric distribution, where the distribution itself has the geometric form (https://mathworld.wolfram.com/GeometricDistribution.html, around equation 6).

I agree that the Li function seems like a detour, but maybe it can make some of the manipulation easier?

And since it's discrete, you can use finite differences.

  a =  sum_1 n^3 / 2^n 
    = sum_0 (n+1)^3 / 2^(n+1)
    =  (1/2) (1 + sum_1 (3n^2 + 3n + 1)/2^n)
    
  b = sum_1 n^2 / 2^n  
    = (1/2) (1+ b + sum_1 (2n +1)/2^n)

  c = sum_1 n / 2^n  
    = (1/2) (1+ c + sum_1  1 / 2^n)

  d =  sum_1 1 / 2^n  
    = sum_0 1 / 2^(n+1)
    = (1/2) (1 + d)
    = 1


  d = 1               =             1
  c = d +  1          = 1+1      =  2
  b = d + 2c +  1     = 1+1+4    =  6
  a = d + 3c + 3b + 1 = 1+1+6+18 = 26

In general,

  f_k = sum n^k/2^n 
      = (*k*th row of Pascal's triangle)•(f_0, ..., f_{k-1},1)

https://oeis.org/A000629

Number of necklaces of partitions of n+1 labeled beads.

Mathologer video on the same: https://www.youtube.com/watch?v=4AuV93LOPcE

This is pretty neat! I was toying around with the problem and it appears you can use generating functions to derive the same sequence of operations. If you start with:

  G(x) = 1 + x + x^2 + ... = 1/(1-x)

The coefficients of this polynomial is the sequence (0^0, 1^0, 2^0, ...)

If you take the derivative of G(x) and multiply by x you get:

  x * G'(x) = x + 2*x^2 + 3*x^3 + ... = x * d/dx 1/(1-x) = x/(1-x)^2

The coefficients of this polynomial is the sequence (0^1, 1^1, 2^1, ...). If you repeat this step, you get a polynomial whose coefficients are (0^2, 1^2, 2^2, ...) and if you do this operation N times, you can get a closed form of a polynomial whose coefficients are (0^N, 1^N, 2^N, ...).

The infinite sum converges for -1 < x < 1. If you set x=1/c, you get the infinite sum

  0^N/c^0 + 1^N/c^1 + 2^N/c^2 + ...

which is exactly the sum we are trying to solve for. This means you solve any infinite sum of the form given by taking the derivative of 1/(1-x) N times while multiplying by x each time. Then plug in x=1/c at the end.

Doing it with generating functions is essentially the same as what is done in the post under a different name.

True, but the generating functions make it easier to prove that this works, rather than relying on the properties of a particular function (properties that you can most easily prove by reverting to the generating functions).

Aside: it looks like the c=2 case generates only integers, and it's an OEIS sequence which shows up in a lot of combinatorics problems,

https://oeis.org/A076726 (" A076726 | a(n) = Sum_{k>=0} k^n/2^k")

https://oeis.org/A000629 ("A000629 | Number of necklaces of partitions of n+1 labeled beads")

I found it useful to walk through evaluation of a few elementary instances of this class using simpler methods, to put the main result in perspective. Specifically, replace the initial 3 exponent with 0 or 1.

If the exponent is 0, then you have the sum 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ..., from Zeno's most famous paradox (https://en.wikipedia.org/wiki/Zeno%27s_paradoxes ). If you are fortunate, you previously learned that this converges to 1, and played around with this enough in your head to have a solid understanding of why. If you are less fortunate, I recommend pausing to digest this result.

Then, if the exponent is 1, you have the sum 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ... .

What happens if we subtract (1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ...) from it? We have (1/4 + 2/8 + 3/16 + 4/32 + ...) left over.

Then, if we subtract (1/4 + 1/8 + 1/16 + 1/32 + ...) from the latter, we still have (1/8 + 2/16 + 3/32 + ...) left over.

Then, if we subtract (1/8 + 1/16 + 1/32 + ...) from the latter, we still have (1/16 + 2/32 + ...) left over.

Continuing in this fashion, we end up subtracting off

(1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ...) + (1/4 + 1/8 + 1/16 + 1/32 + ...) + (1/8 + 1/16 + 1/32 + ...) + (1/16 + 1/32 + ...) + (1/32 + ...) + ...

and this converges to the main sum. And, from the exponent-0 result, we know this is just 1 + 1/2 + 1/4 + 1/8 + 1/16 + ...

Hi in the 3rd equation you meant to write Li_s(z) but you wrote x instead.

That was an interesting article thanks.

Also:

> ... so Li_s(z) is a rational function of z whenever s is a non-negative integer.

I believe that should be "negative" rather than "non-negative".

Thanks. Fixed.

Fun stuff. A good follow-up is the book: A = B, by Marko Petkovsek, Herbert S Wilf, Doron Zeilberger, A K Peters/CRC Press, 1996.

It feels odd the sum of the first example is 26. (All the number nerds, please forgive me). It's such a usual number.

From my read, it probably flows from 26 = 27 - 1 = 3^3 - 1, given the equation is looking at cubes.

It's not. (Law of Small Numbers)

As the exponent k in the denominator grows, the sum is approximately k! (factorial)

https://oeis.org/A000629

The answer is just 26? That’s crazy.

Wonder if there’s any way to intuit this before working it out.

There are some "double counting" techniques which lead to very intuitive solutions. Perhaps one could find such a solution.

https://oeis.org/A000629

Number of necklaces of partitions of n+1 labeled beads.

[Comment removed by author]

This is exactly the approach described in the article.

Yes, sorry -- I did not realize that for some reason. I removed my comment.

Off-topic question: I’m using the iOS browser extension Noir, which adds dark-mode support to web sites that don’t support dark mode by themselves. However, this causes MathJax(?) formulas like in the article to be displayed black on black. Does anyone know of a similar browser extension that can handle this? (And yes, I already reported this issue to Noir some time ago.)

The Dark Reader extension with Firefox has the same problem.

I believe the SVG file has a transparent background, but the img tag has style="background-color:white". Some browsers honor the background-color setting and show a white background behind the equations, even in dark mode. Some do not, and so the equations appear as black-on-black.

It would be better if I altered the SVG image itself to set the background color, but I don't know how to do that. Suggestions are welcome.

Displaying black on white in dark mode is still bad. In principle, CSS invert() should be able to do the trick for SVGs. You’d have to test it on all relevant browsers though.

Not even that, you should just use currentColor rather than black in SVGs.

Depends on whether you have control over the SVG contents or not.

Why would you not have control over the markup of your own website?

the title makes this seem like some major or original discovery in math. Try evaluating the logarithmic integral with positive n , like r^3/n^3 instead of n^3/r^3. Way harder and more interesting.

I strongly disagree. It's an accurate description of the content of the essay, and it's clear from the first line that it's something new/surprising to the author, not something new to mathematics.

There are lots of things which are harder to compute. There are lots of things which can be more interesting. So what? It just means that you are not the target audience for this blogger, and your disdain comes across as snobbishness.

Reply on news.ycombinator.com