## Wednesday, October 26, 2005

### a puzzle

Is there a closed-form expression of some kind corresponding to the formal power series

∑ x2k
k = 0

1. Yep, the answer is 42.

Posted by Anonymous

2. This type of summation showed up in my thesis (available on-line), where I was looking at the limit as x goes to 1. It's proprtional to log (1-x)^{-1}, funnily enough, if I'm remembering right.

Now that I've plugged my thesis, the info you really want seems available in Gonnet/Yates, Handbook of Algorithms and Data Structures, a rather unappreciated and highly useful book. On my copy it's page 303; Equation II.33 in Appendix 2. It's ugly enough I won't write it here.

Posted by Michael Mitzenmacher

3. Looks like Micharl beat me to it, I blame the time difference with the west coast. I don't have access to the book, but here's a simple handwavy proof for the bound.

Let x = (1-\eps). We know that for x < 0.9 (say) the summation is bounded by a small constant.

Now consider expanding the sum until x^{2^i} = 0.9

(1-\eps) + (1-\eps)^2 + (1-\eps)^4 + ...

(1- \eps) + (1-2\eps) + (1-\4eps) + ...

the number of terms needed to get to 0.9 is something like \log(1/eps), and the result follows.

Posted by Anonymous

4. Thanks all ! I knew someone would know the answer !! Now if only I could also solve my research questions this way ;)

Posted by Suresh

5. Now if only I could also solve my research questions this way ;)

that is called the "lazyweb" ;)

Posted by Anonymous

6. the info you really want seems available in Gonnet/Yates, Handbook of Algorithms and Data Structures, a rather unappreciated and highly useful book.

If it is any consolation, I understand both the first and second editions sold like pancakes when they came out, bought out mostly by practicioners. Theoreticians seem to pretty much have ignored it.

Posted by Anonymous