The predecessor trees must contain all the integers if the Collatz conjecture is true. There turn out to be a large number of different ways to determine the total content of the abstract predecessor tree. Some are so generic as to be of little more than passing interest. These are given first. Eventually we capitalize on various threads of information gleaned along the way to make much more satisfying "counts".

The prose here often repeats in good measure the arguments already given elsewhere. Perhaps this may be excused as an attempt to reach readers who are not quick to grasp and piece together the various elements of argument here.

A word of explanation may be helpful. Everything we are "counting" here is infinite. We don't really count to infinity. Instead we use more indirect approaches. In the first portion of the following, we count paths as they are formed in the abstract predecessor tree. Subsequently, we take advantage of the complete subsetting of the nodes of the abstract predecessor tree and the formulas which characterize each subset (anchored at both top and bottom so that they are unique) to calculate the densities of the integers contributed by each and show that the densities of the subsets add correctly to account for all the odd integers >=3. When we add up the contributions by the members of various sets among the odd integers in order to show that the contributions sum to all the odd integers, we base the summations on different starting sets so the sums may be 1/2 or 1 or 2 or 3 or 4, as appropriate in each case. Each summation could easily be rescaled, but it would introduce an unnecessary awkwardness in the introduction of each instance.

The Maple V Computer Algebra System was used extensively in this work. Results lifted from Maple V sessions are included below (and elsewhere in these pages) with a Maple command prefixed by a greater than sign (">") and the Maple response centered immediately below.

First we will consider the paths developed from the elements of the extensions set. There should be a termination for every path even though the paths may be arbitrarily long.

The abstract predecessor tree starts with an infinite set of extensions whose values modulo 3 are in {0, 1, 2}. One-third of these (those congruent to 0) bear no left descents (hence are called leaf nodes) and may be immediately regarded as finished paths. The other two-thirds fall into two equal-sized disjoint sets whose members are congruent to 1 or 2 modulo 3. Their elements are all the parents of children, hence continued paths. These children are equally {0, 1, 2} modulo 3 and will be subdivided for further development of the paths of the predecessor tree identically. Thus, one-third of each of the two branches (i.e. 2/9 in all at this level) are barren (leaf nodes) , and represent newly terminated paths. This process continues iteratively. In the next stage there are 4 disjoint subsets in which 1/3 are leaf nodes, totaling 4/27 of paths terminated at this level. Thus, the terminated paths accumulate as 1/3 + 2/9 + 4/27 + ... as the predecessor tree is constructed level by level. Inductively, we expect an infinite descent with terminated paths accumulating as the sum of 2**i/3**(i+1).

Assertion: this formulation applies whether we are considering the infinite set of elements in the extension set of any integer or the totality of the elements of all the extension sets in the predecessor tree. The validity of this shift of viewpoint may be questionable. We will argue later that it is justified.

> sum(2**i/3**(i+1), i=0 .. infinity);

1

There are as many paths to leaf nodes as there are extensions. Considered in the small, this says the elements at any stage in the predecessor tree will eventually reach a leaf node to terminate its path. Considered as a totality, this encompasses all the leaf nodes in the predecessor tree including the barren elements in the extension sets. All left descents terminate. We started by assuming that only extensions head left descents, and now we see that every left descent terminates at length. Could it be that all those left descents actually contain all the odd integers?

> sum(2**i/3**i, i=0 .. infinity);

3

This expresses the total content of the predecessor tree dependent from the parental extension nodes in terms of the content of the parental set. There are three times as many left descent elements as there are extension elements. Since 1/4 of the odd integers are congruent to 5 mod 8, this establishes that there is the correct density of left descent elements.

Let's complete the balance sheet by accounting for the internal left descent elements, those which are parental to another left descent element. The difference between the entirety of each level (2^i/3^i) and the leaf nodes in it (2^i/3^(i+1)) will give the internal nodes in it. This expression simplifies as follows to a ratio of powers of 2 and 3.

> 2**i/3**i - 2**i/3**(i+1);

i i 2 2 ---- - -------- i (i + 1) 3 3

> simplify(");

(i + 1) (-i - 1) 2 3

And that expression, 2**(i+1)/3**(i+1), may be summed to discover the total number of internal nodes in the Collatz predecessor tree as a multiple of the number of elements in the extensions.

> sum(2**(i+1)/3**(i+1), i=0..infinity);

2

This just reinforces (what we already knew) that the 1/3 of all non-extension nodes which are congruent to 0 mod 3 are leaf nodes and the other 2/3, those congruent to 1 or 2 mod 3, are child-bearing and therefore internal to the tree.

The summations show that the left descents account for three times as many odd integers as the {8n+5} extensions. The extensions account for one-quarter of the odd integers. In the left descents, 2 times as many nodes are internal as are leaves. Together the leaves and internal nodes in the predecessor tree constitute the 3/4 of the odd integers not accounted by the extensions. Thus, the entire set of odd integers is accounted for. Not only have we been able to characterize the extensions and the left descents in terms of the subset of integers which constitute them, we have also accounted for their proportions in a consistent way.

In support for the just preceding and the following paragraphs, we must point out that the densities being added in every case are constant across the orders of magnitudes. Thus, the density of integers congruent to 5 mod 8 (aka 'in {8n+5}') among the odd integers is 1/4. The only precaution we need take is to sample exactly 4 or a multiple of 4 consecutive odd integers. We will find that 1/4 of the sample is always congruent to 5 mod 8 and the other 3/4 is not. This will be true whether we look at small numbers or immense numbers, and whether our first sampled odd integer is congruent to 1, 3, 5, or 7 mod 8 because the residues cycle through their values in a fixed order. Every formula of the form d*n+c will have a density of representatives equal to 1/(d/2) or 2/d, provided only that d/2 consecutive odd integers are inspected and independent of the phase of the sampling. Since we want to sample the integers fairly, we will always start at 3.

Of course, when we add the densities, we must assure ourselves that the sets which are used in establishing them do not overlap, else there would be an overcount made.

We turn now to the figures which represent the complete down and up-again development of the formulas representing the contents of all the subsets in the predecessor tree when separated into the subsets contained in the various completed left descents. We wish to capitalize on the 1:1 mapping of leaf nodes back up the paths to their origins in the extensions to show that the extensions and the leaf nodes are 1:1. If that can be shown, then the utility of the set of all extensions as the root node in the abstract predecessor tree is supported. Unfortunately there is still no assurance that some of the extensions included in the root node are not actually ones in the tree of counter examples. It turns out that this viewpoint gives the same result as summing all the leaf nodes in the tree, but this time we are can see more clearly that the contribution of subsets to every parental node all the way up to the extensions behaves just as we observed for the entire tree earlier.

The rightmost filled column in each row of the
up-again process represents the subsets of the 8*n*+5 set whose destiny
has been worked out down to a depth of three or four. The density of
"*et*" leaf set is exactly that 1/3 of the 8*n*+5 set which is
congruent to 0 mod 3. Each of the entries in the second column, the
"*ebt*" and "*est*" sets, second and third rows, represent
densities of exactly 1/9 of the original 8*n*+5 set but there are
two of them. Each of the entries in the third column, rows three
through six, represent exactly 1/27 of the density of the original
8*n*+5 set but there are four of them. Of the eight sets each
accounting for 1/81 of the original 8*n*+5 set only three are
shown, but there are eight of them. Clearly this relationship will
continue indefinitely and we may sum the fractions of the odd integers
which will be covered in all.

> sum(2^*i*/3^(*i*+1),* i*=0..infinity);

1

Thus, the sets constituting the abstract predecessor tree are completely subsetted and accounted for by projecting subsets identified from leaf nodes back into them. That is not a different summation, but it arises from a different viewpoint from that which first resulted from a count of the number of leaf nodes descendent from the extensions. Perhaps this could be regarded as an indication that the paths from extension to leaf node do not branch; there is an undeviating path from extension node to leaf node for each path.

All the above summations use the paths in the predecessor tree
level-by-level to account for the integers identified in various ways.
However, the predecessor tree is lop-sided since, in any given
generation, the integers reached in the left side where *s* steps
predominate are smaller than those reached in the right side of the tree
where *b* steps predominate. In other words, the density of
integers reached by equally long paths with predominately *s* steps
is greater than those reached by paths with predominately *b*
steps. This suggests that a more satisfying accounting might result if
the summation were done using a view of the tree which was more balanced
in terms of the magnitude of numbers reached.

Fortunately, the distribution of
cardinalities of formulas bearing successive values of *a* for a
given value of *b* in the coefficients, 2^*a**3^*b*, over
a very large set of such formulas (where the Fibonacci series makes an
appearance) provides exactly such a basis. The reason the
Fibonacci numbers appear is evident upon
inspection of the selection of sets of binomial coefficients which apply
to any given power of 2 depth. This relationship is
fully explored elsewhere on the web.

Furthermore, the various
fractions of the Fibonacci series which appear for a given value of
*b* in that table of cardinalities have
closed sums because the sum(F(*i*)/2^(*i*+1),*i*=1..infinity)
is 1, where F(*i*) are the Fibonacci numbers. I.e.
the sum of 1/4
+ 1/8 + 2/16 + 3/32 + 5/64 + 8/128 + 13/256 + ... is 1. A related
infinite sum substituting 10 for 2 in the denominator has been fully explored
. Substituting 2 for 10 in the derivation gives 1/(4-2-1) or 1/1 in the penultimate
step, thus proving the above relationship.

The contribution of the density of the integers in each cell in the
relevant table to the total number of integers
is its entry (its frequency of occurrence) divided by
2^*a**3^*b* (its density among the integers). Each row will
make a smaller contribution than that of the Fibonacci series sum
in the inverse ratio to that of its divisor to 4, the first
denominator in the Fibonacci sum, above. For the first row
(*b*=1), the first divisor is 24, or six times the first
denominator in the Fibonacci summation, so the first row (whose
cardinality starts at 1) contributes 1/6 of the density of the integers.
For the second row (*b*=2), the first divisor is 72, or 18 times
the first Fibonacci denominator, but the weight is 2 (since the
cardinality starts at 2), so 2/18 or 1/9 is contributed to the density
of the integers. For the third row (*b*=3), the first divisor
is 216, 54 times the first Fibonacci denominator, and the weight is 4,
so 4/54 or 2/27 is contributed to the density of the integers. For the
fourth row (b=*4*), the first divisor is 648, 162 times the
first Fibonacci denominator, the weight is 8, so 8/162 or 4/81 is
contributed to the density of the integers. Continuing on, it becomes
evident that the second and subsequent rows are contributing
2^*i*/3^(*i*+2) each. Even the initial row fits this at i=0, so the total
density will be the sum(2^*i*/3^(*i*+2),*i*=0..infinity) or 1/2,
or just enough to cover all the odd integers.

There is no possibility that even integers confuse accounting since the whole genesis of the table is concerned with odd integers only.

This summation adds no new information to that obtained above -- it continues to say that all the odd integers are reached. Since it was obtained from a much more detailed analysis and a deeper level of insight it should be regarded as a stronger result. Also it is pleasing to be looking at a more nearly "balanced" tree in terms of the magnitude of numbers reached at any given depth.

These ideas will receive a still more thorough discussion in a later section devoted to examining various finite sums of the contents of the abstract tree and of the cardinality table.