## Harmonic Sums of Integers With k Binary 1's

If S(k) denotes the sum of the inverses of the odd natural numbers
whose binary representations contain exactly k ones, I conjectured
that S(k) approaches ln(2) as k increases to infinity, whereupon
Robin Chapman pointed out a simple proof involving some nice
elementary manipulations of infinite series.
Let b(r) denote the number of ones in the positive integer r's
binary representation. If s is an odd integer with b(s)=k, then
obviously multiplying s by any power of 2 won't change the number
of binary 1's, so it follows that b(2^t s)=k for any non-negative
integer t. Thus, for each odd number s with b(s)=k there are
infinitely many even numbers with the same number of 1's in their
binary representations, of the form 2^t s with s=1,2,3,..., so
the sum of their reciprocals (1/s) times (1/2 + 1/4 + 1/8 + ...),
and this factor equals 1. Therefore, we've shown that the sum of
the reciprocals of all the odd numbers with exactly k 1's in their
binary representations is equal to the sum of the reciprocals of
all the even numbers with exactly k 1's.
Now we observe that an integer s is even with b(s)=k if and only if
s+1 is odd with b(s+1)=k+1. Consequently, if we let S_e(k) denote
the sum of reciprocals of all even numbers with k binary 1's, the
quantity
S(k) - S(k+1) = S_e(k) - S(k+1)
is the sum of 1/s - 1/(s+1) as s ranges over all even numbers with
b(s) = k.
Now suppose we evaluate the sum of S(k) - S(k+1) over ALL positive
integers k. This means that we need to evaluate the sum of 1/(s(s+1))
over ALL even s, so we have
inf / \
SUM ( S(k) - S(k+1) ) = (1/2 - 1/3) + (1/4 - 1/5) + ...
k=1 \ /
= 1 - ln(2)
Notice that the left hand terms of the summation have the form
[S(1) - S(2)] + [S(2) - S(3)] + [S(3) - S(4)] + ...
so the nth partial sum is just S(1) - S(n), and therefore the
infinite sum is S(1) - lim{k->oo} S(k), which equals 1 - ln(2).
Since S(1) is just 1, it follows that lim{k->oo} S(k) = ln(2).

Return to MathPages Main Menu