This post has more explanations in it if the previous post is harder to understand. It also is longer to read since some of the explanation parts are more explicit and some ideas are restated when needed.
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)].
This consolidates the C in the formula and creates an expression in terms of the largest variable (D) and other variables (E, F, G...) which is in the numerator while it has only C and D in the denominator. The effect this has is that if you add 1 to D, E, F, G..., then that term doubles since each term is 2 to its variable part. (Note that this would work with any variable besides C, but then some powers would come out negative.)
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. The effect of this happening is in each chunk, we know what A(n) is, and so all we have to worry about is B(n) values, and B(n) values taken as a chunk can be more easily simplified without the A(n) values around.
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 adds 1 to the B values, and thus 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).
That may look confusing, but it really is simple. Here is a visual way to look at it. Notice that the exponents on the 2 from the previous chunk go on the left side untouched and on the right side plus 1. (1 is somewhat of a special case since there it only consists of 1 term.)
1 has a numerator of 2^0 = 1 = 3^0.
1: 10 and 11: 2^(0) + 2^(0+1) = 3 = 3^1.
10: 100 and 101: 2^(0) + 2^(0+1) +
11: 110 and 111: 2^(1) + 2^(1+1) = 9 = 3^2.
100: 1000 and 1001: 2^(0) + 2^(0+1) +
101: 1010 and 1011: 2^(1) + 2^(1+1) +
110: 1100 and 1101: 2^(1) + 2^(1+1) +
111: 1110 and 1111: 2^(2) + 2^(2+1) = 27 = 3^3.
Noticing this induction formula, this means Z(n) triples each time and so Z(n)=3^n.
The largest number of 1s that can exist in a number is equal to A(n), so D=A(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:13 |
Chunking A(n) -- Explained
