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