NHacker Next

- new
- past
- show
- ask
- show
- jobs
- submit

login

Rendered at 17:11:14 GMT+0000 (Coordinated Universal Time) with Vercel.

NHacker Next

- new
- past
- show
- ask
- show
- jobs
- submit

login

Rendered at 17:11:14 GMT+0000 (Coordinated Universal Time) with Vercel.

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).

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.

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

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?

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

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

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.provethat 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).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")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 + ...

That was an interesting article thanks.

> ... 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".

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

https://oeis.org/A000629

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

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

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.

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.