[math-fun] Binary tree of divisions of natural numbers (was: Problem I never solved)
Adam P. Goucher: It's equivalent to showing that the limit of the series: Sum[(-1)^h(n) (log(2n + 1) - log(2n + 2))] (where n ranges from 0 to infinity) is -log(2)/2, where h(n) is the Hamming weight of n. Interestingly, there is a similar result on polynomials (known as Flanelle's theorem, and rather easy to prove): Sum[(-1)^h(n) p(n)] (where n ranges from 0 to 2^k - 1) = 0 for any polynomial p(n) of degree at most k-1. Can we use Flanelle's theorem together with Weierstrass approximation to prove anything? --WDS: Fascinating. It seems a bit simpler to phrase it as S(N) = Sum[ (-1)^h(n) * log(3+n), for n=0...N] Well, first of all, this is a DIVERGENT SERIES i.e. most definitely S(N) has no limit as N-->infinity. Although Goucher's version is less divergent, it is not completely clear to me that it converges. Second, we CAN use "Flanelle's theorem" (which also sounds fascinating & I am taking it from APG on trust -- I'd never heard of it) to prove that the limit of S(N) DOES exist if we take N-->infinity ALONG the sequence 1,3,7,15,31,63,... which, by the way, is what is "equivalent" to Wilson's ask. To prove that: use as a lemma, the fact that the function ln(1+x) has a degree-k polynomial approximation which, within the interval 0<x<1, has maximum |error| of order <= 3^(-k). To prove the lemma, use the Taylor series based at x=1.5. (Actually, by using the Chebyshev series, which also is known is closed form, we could prove an exponential multiplication factor smaller than 1/3, but we shall not need to.) Now use Flanelle to see that the subsum from n=2^k to 2^(k+1)-1, is equal to zero, plus an error term. The zero arises from the polynomial approximation of the ln, via Flanelle. The error arises from summing the error in that approximation. This summed error is of order (2/3)^k and hence the sequence of subsums has exponentially dying absolute values, proving convergence. QED. This also allows you (with a bit more trouble) to write explicit error bounds, which would allow you via a finite computation to prove the alleged equality with -ln(2)/2 is FALSE (if it is) or to prove it is "true within +-0.00001" (if it is). ------------------------------Re the revised title of this post: Write the numbers 3 4 5 6 7 ... on a line. Regard them as the leaves of an infinite balanced binary tree. Each node of the tree has value a/b, where a is its left child and b its right child. David Wilson's problem is to prove or disprove that the sequence of values along the leftmost path in this tree, converges (as we walk along path away from the leaf "3") to sqrt(2)/2. With any other operator {*, +, -} in place of "/", understanding this sequence would be trivial. Adam P Goucher's observation was that the sequence of logs of these values is the (k-1)th value of S2(N) = Sum[(-1)^h(n) (log(2n + 1) - log(2n + 2))] summed from n=1 to 2^k. My simpler (?) version of same observation involves S1(N) = Sum[ (-1)^h(n) * log(n+3) ]. We can also go in the other direction, e.g. S4(N) = Sum[(-1)^h(n) (log(4n - 1) - log(4n) - log(4n+1) + log(4n+2))]. This last version has the advantage that this series really is manifestly obviously convergent. And if we go further in this "direction," we would get more-rapidly-convergent formulations S8(N) etc, albeit with more complicated summands.
participants (1)
-
Warren D Smith