Associated Topics || Dr. Math Home || Search Dr. Math

### 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

- Doctor Pete, The Math Forum
Check out our web site! http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search