Published October 28, 2020｜2 minute read

Here’s a nice solution of Putnam 1981 B5 that I haven’t seen anywhere else (so far). The main idea is to sum `bitwise,' rather than `termwise.'

Let SkS_k denote the set of positive integers with the kthk^{\text{th}} bit set, counting from the right starting at k=0k=0. Then we have

∑n=1∞B(n)n2+n=∑k=0∞∑n∈Sk1n2+n.\sum_{n=1}^\infty \frac{B(n)}{n^2 + n} = \sum_{k=0}^\infty \sum_{n \in S_k} \frac{1}{n^2 + n}.

A bit of thinking shows that n∈Skn \in S_k if and only if ⌊2−kn⌋=2m+1\lfloor 2^{-k} n \rfloor = 2m+1 is odd. Thus the sum becomes

∑k=0∞∑m=0∞∑n=2k (2m+1)2k (2m+2)−11n2+n.\sum_{k=0}^\infty \sum_{m=0}^\infty \sum_{n=2^k \, (2m+1)}^{2^k \, (2m+2) - 1} \frac{1}{n^2 + n}.

Since (n2+n)−1=n−1−(n+1)−1(n^2 + n)^{-1} = n^{-1} - (n+1)^{-1}, the inner sum telescopes, yielding

∑k=0∞12k∑m=0∞[12m+1−12m+2]=2ln⁡2.\sum_{k=0}^\infty \frac{1}{2^k} \sum_{m=0}^\infty \left[\frac{1}{2m+1} - \frac{1}{2m+2}\right] = 2 \ln{2}.