Summing a Binary Function SequenceDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/