The proof given here is based on splitting the interval [1, n] in a very special way, patterned after a discussion by Eppstein. In the end, we take the limit as n approaches infinity, so it is best to think of n as large. The penultimate step of our analysis is an infinite series representation for the double-free set constant: (1/2) * ( 1*(1 - 1/2) + 1*(1/2 - 1/4) + 2*(1/4 - 1/8) + 2*(1/8 - 1/16) + 3*(1/16 - 1/32) + 3*(1/32 - 1/64) + 4*(1/64 - 1/128) + 4*(1/128 - 1/256) ... ) In the final step, this is easily shown to sum to 2/3, as was to be proved. Let us explain, for example, how the 4*(1/128 - 1/256) term arose. First, consider all odd integers m satisfying n/256 <= m <= n/128. To each of these integers m, associate a linear graph with 8 vertices: m - 2m - 4m - 8m - 16m - 32m - 64m - 128m The coefficient 4 in the 4*(1/128 - 1/256) term arises since 4 is the independence number of the graph. The independence number is defined to be the maximum possible cardinality of non-adjacent vertices. The factor 1/128 - 1/256 arises since this is the proportion of of integers from [1, n] which fall in [n/256, n/128]. Let us now do a smaller example. Consider all odd integers m satisfying n/8 <= m <= n/4. To each of these integers m, associate a linear graph with 3 vertices: m - 2m - 4m The coefficient 2 in the 2*(1/4 - 1/8) term arises since 2 is the independence number of the graph. The factor 1/4 - 1/8 arises since this is the proportion of integers from [1, n] which fall in [n/4, n/8]. Each of these linear graphs are disconnected fragments of a much larger graph G. The graph G encodes information about the interval [1, n]. Each fragment includes only certain values up to n, and each value from 1 to n is included in exactly one such fragment. Our analysis is based on the simple observation that we can choose the optimal subset independently in each fragment without worrying about what's happening in any other fragments. After this, we add together all the independence numbers multiplied by the correct proportionalities. The initial coefficient 1/2 comes from the fact that we have fragments associated only with odd integers m. One last note: the two linear graphs mentioned above could more simply be written as 1 - 2 - 4 - 8 - 16 - 32 - 64 - 128 and 1 - 2 - 4 as if we omitted m. We'll adopt this shorthand notation in subsequent discussions.
Copyright (c) 2002 Steven R. Finch.
All rights reserved.