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).
jwmerrill 28 days ago [-]
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.
lupire 28 days ago [-]
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)
To be honest, the whole use of the Li function before defining it made me stop reading.
mturmon 28 days ago [-]
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?
malisper 28 days ago [-]
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.
ajkjk 28 days ago [-]
Doing it with generating functions is essentially the same as what is done in the post under a different name.
shiandow 27 days ago [-]
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).
perihelions 28 days ago [-]
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,
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
Number of necklaces of partitions of n+1 labeled beads.
eddd-ddde 28 days ago [-]
There are some "double counting" techniques which lead to very intuitive solutions. Perhaps one could find such a solution.
khana 28 days ago [-]
[dead]
cafaxo 28 days ago [-]
[Comment removed by author]
Chinjut 28 days ago [-]
This is exactly the approach described in the article.
cafaxo 28 days ago [-]
Yes, sorry -- I did not realize that for some reason. I removed my comment.
layer8 28 days ago [-]
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.)
vitehozonage 28 days ago [-]
The Dark Reader extension with Firefox has the same problem.
johndcook 28 days ago [-]
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.
layer8 28 days ago [-]
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.
xigoi 27 days ago [-]
Not even that, you should just use currentColor rather than black in SVGs.
layer8 26 days ago [-]
Depends on whether you have control over the SVG contents or not.
xigoi 26 days ago [-]
Why would you not have control over the markup of your own website?
28 days ago [-]
paulpauper 28 days ago [-]
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.
eesmith 28 days ago [-]
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.
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.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.