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 grouped the terms in S with equivalent A(n) values to sum the terms, using the formula (1/2)^[C+D] + (1/2)^[C+E] + (1/2)^[C+F] + (1/2)^[C+G] equals [1+2^(D-E)+2^(D-F)+2^(D-G)]/[2^(C+D)].

Chunk the terms so the terms with the same A(n) value are together. This allows the Cs to recur and since A(n) has n digits, C=n.

To figure out what the sum of the terms with the other variables equal (each respective B(n), instead the amount of zeroes in the number must be computed, since the exponent consists of the variable subtracted from D. (Since D is the largest amount of 1s possible, it equals A(n) since a number could have all 1s and thus, taking the amount of possible 1s minus the number of existing 1s gives the amount of digits that aren't 1, namely 0.) This can be proven inductively: (Z(n) is the numerator in the resulting fraction for each chunk) 

For Z(1), the only B(term) is B(1) with 0 0s equalling 1, which is 3^0.

For Z(n), the digits in Chunk n are the same as two copies of Chunk (n-1), one with an extra 1 at the end which does nothing to the B values, and one with an extra 0 at the end, which doubles the power terms in the top formula.  This means the Z(n)=Z(n-1)+2Z(n-1) or Z(n)=3Z(n-1).

Noticing this induction formula, this means Z(n) triples each time and so Z(n)=3^n.

Using these ideas to complete the formula gives [3^(n-1)]/[2^(2n)]=3^(-1)*(3/4)^(n), and by using the formula for summing geometric sequences (where 1/3*3/4=1/4 is the first term and 3/4 is the successive ratio) it gives (1/4)/(1-3/4)=1.

Posted by Gamer on 2005-08-21 04:11:25