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 Sk denote the set of positive integers with the kth bit set, counting from the right starting at k=0. Then we have
n=1∑∞n2+nB(n)=k=0∑∞n∈Sk∑n2+n1.
A bit of thinking shows that n∈Sk if and only if ⌊2−kn⌋=2m+1 is odd. Thus the sum becomes
k=0∑∞m=0∑∞n=2k(2m+1)∑2k(2m+2)−1n2+n1.
Since (n2+n)−1=n−1−(n+1)−1, the inner sum telescopes, yielding
k=0∑∞2k1m=0∑∞[2m+11−2m+21]=2ln2.