For each positive integer n, let A(n) be the number of digits in the binary representation of n, and let B(n) be the number of ones in the binary representation of n. What is the value of S:

S = (1/2)^[A(1)+B(1)] + (1/2)^[A(2)+B(2)] + (1/2)^[A(3)+B(3)] + ...

I think the sum must be exactly one. Here's why:

First, A(2n) = A(n) + 1 (multiplying a number by two in binary adds a zero to the end so the digit count increases by exactly one).

Next, B(2n) = B(n) (we added a zero, so the 1 count is the same)

Also, A(2n+1) = A(n) + 1 (since multiplying by two added a zero on the right, adding one changes the zero to a one with no change in digit count)

And B(2n+1) = B(2n) + 1 (since this time we added a 1 on the right)

Now, let's define C(n) = A(n) + B(n). C(2n) = C(n) + 1 and C(2n+1) = C(n) + 2.

Consider two consecutive terms in the sequence where the first term has n even. These must be (1/2)^C(2n) + (1/2)^C(2n+1) for some n, which is equal to (1/2)^(C(n) + 1) + (1/2)^(C(n)+2) = (1/2)(1/2)^C(n) + (1/4)(1/2)^C(n) = (3/4)(1/2)^C(n).

This is true for all n, so the entire sum S can be written as (1/2)^C(1) + (3/4){the original sequence}. Or, since C(1) = 2, S = 1/4 + (3/4)S. Solving for S trivially gives S=1.

The key to this approach appears to be that by treating consecutive pairs of the sequence as a unit (after the first) we get back a multiple of the original sequence, much like solving an infinite continuing fraction problem.

Posted by Paul on 2005-08-20 20:32:01