[HN Gopher] Evaluating a class of infinite sums in closed form
___________________________________________________________________
Evaluating a class of infinite sums in closed form
Author : beefman
Score : 117 points
Date : 2024-08-04 00:20 UTC (22 hours ago)
(HTM) web link (www.johndcook.com)
(TXT) w3m dump (www.johndcook.com)
| playingalong wrote:
| It feels odd the sum of the first example is 26. (All the number
| nerds, please forgive me). It's such a usual number.
| gaogao wrote:
| From my read, it probably flows from 26 = 27 - 1 = 3^3 - 1,
| given the equation is looking at cubes.
| fsmv wrote:
| Hi in the 3rd equation you meant to write Li_s(z) but you wrote x
| instead.
|
| That was an interesting article thanks.
| teraflop wrote:
| 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".
| johndcook wrote:
| Thanks. Fixed.
| johndcook wrote:
| Thanks. Fixed.
| perihelions wrote:
| 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"_)
| layer8 wrote:
| 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 wrote:
| The Dark Reader extension with Firefox has the same problem.
| johndcook wrote:
| 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 wrote:
| 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.
| paulpauper wrote:
| 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 wrote:
| 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.
| cafaxo wrote:
| [Comment removed by author]
| Chinjut wrote:
| This is exactly the approach described in the article.
| cafaxo wrote:
| Yes, sorry -- I did not realize that for some reason. I
| removed my comment.
| chrchang523 wrote:
| 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 + ...
| WhitneyLand wrote:
| The answer is just 26? That's crazy.
|
| Wonder if there's any way to intuit this before working it out.
| eddd-ddde wrote:
| There are some "double counting" techniques which lead to very
| intuitive solutions. Perhaps one could find such a solution.
| malisper wrote:
| 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 wrote:
| Doing it with generating functions is essentially the same as
| what is done in the post under a different name.
| pontus wrote:
| 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 wrote:
| 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.
| amelius wrote:
| To be honest, the whole use of the Li function before
| defining it made me stop reading.
| mturmon wrote:
| 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?
| lupire wrote:
| 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.
___________________________________________________________________
(page generated 2024-08-04 23:00 UTC)