Summing a Binary Function Sequence

Date: 07/16/98 at 15:56:16
From: Mark Ping
Subject: Calculate the sum of a sequences

Dear Dr. Math,

Here is the question:

   Compute

    oo
   ----
   \      B(n)  
   /    --------
   ----  n(n+1)
    n=1

where B(n) denotes the sum of the binary digits of n.

Thanks,
Mark Ping

Date: 07/19/98 at 22:56:18
From: Doctor Pete
Subject: Re: Calculate the sum of a sequences

Hi,

Interesting question! The key to solving this problem is to find a 
relation describing the function B(n). In particular, writing out a  
table of B(n) vs. n for small n helps:

   n :   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
   B(n): 0   1   1   2   1   2   2   3   1   2   2   3   2   3   3   4

From this, we might guess that B(2n) = B(n). Thinking about numbers in 
their binary representations proves this is true, since if we write n 
as:

   n = a[k]2^k + a[k-1]2^(k-1) + ... + a[1]2^1 + a[0]

Then a[k], a[k-1], ... a[1], a[0] are the binary digits of n, and:

   B(n) = a[0] + a[1] + ... + a[k]

But:

   2n = a[k]2^(k+1) + a[k-1]2^k + ... + a[1]2^2 + a[0]2^1 + 0

so B(2n) = B(n). In essence, multiplying n by 2 simply shifts the 
binary digits of n one place to the left, and adds a 0 in the units 
digit. Furthermore, from this analysis we see that:

   B(2n+1) = B(2n) + 1

since our previous discussion shows that B(2n) has 0 as the rightmost 
digit.

So, with this in mind, let us write:

   S = Sum[B(n)/(n(n+1)), {n,1,Infinity}]

That is, let S be the sum of B(n)/(n(n+1)) from n = 1 to infinity. 
Then

   S = 1/2 + Sum[B(n)/(n(n+1)), {n,2,Infinity}]
     = 1/2 + Sum[B(2m)/(2m(2m+1)) + B(2m+1)/((2m+1)(2m+2)),               
                                               {m,1,Infinity}]
     = 1/2 + Sum[(B(2m)(m+1)+(B(2m)+1)m)/(2m(m+1)(2m+1)),  
                                               {m,1,Infinity}]
     = 1/2 + Sum[(B(2m)(2m+1) + m)/(2m(m+1)(2m+1)), {m,1,Infinity}]
     = 1/2 + Sum[B(2m)/(2m(m+1)), {m,1,Infinity}]
          + Sum[1/((2m+1)(2m+2)), {m,1,Infinity}]
     = 1/2 + 1/2 Sum[B(m)/(m(m+1)), {m,1,Infinity}] + (2 Log[2] - 1)/2
     = S/2 + Log[2].

It follows that S/2 = Log[2], or S = Log[4]. Here Log means a logarithm 
with base e.

Note I skipped some steps in the above. On the 5th step I separated the 
sum into two components, which I was allowed to do because I knew 
1 < S < 2 (can you figure out why this is true?). Also, in the 6th 
step, I evaluated the second sum:

   Sum[1/((2m+1)(2m+2)), {m,1,Infinity}] = (2 Log[2] - 1)/2

where Log[2] is the natural logarithm of 2. This was done by seeing 
that this sum is actually an alternating series, since:

   1/((2m+1)(2m+2)) = 1/(2m+1) - 1/(2m+2)

and recognizing that Sum[x^k/k, {k,1,Infinity}] = -Log[1-x].  
Substituting x = -1 and moving the first few terms around gives the 
desired simplification. Finally, the last step was observing that we 
managed to simplify the first sum on the right into S itself, thereby 
giving an equation for S. Indeed, we find numerically that:

   1 < Log[4] =~ 1.39 < 2.

Note: =~ means is approximately equal to.

This is a particularly difficult problem, because it is not at all 
obvious how to simplify the summand since we're given so little 
information about the properties of B(n). Furthermore, there is no 
guarantee that the relations B(2n) = B(n), and B(2n+1) = B(2n)+1 will 
be of any use in simplifying the problem. (For example, there are other 
properties of B(n), namely B(2^m + k) = B(k) + 1 for nonnegative 
integers m, k. But this does not help us because it is not immediately 
clear how to take some integer n and express it in the form 2^m + k, 
where m is as large as possible.) Fortunately, in the process of 
manipulating the sum, we find that these properties indeed work to our 
advantage.

- Doctor Pete, The Math Forum
Check out our web site! http://mathforum.org/dr.math/