This is a rather straightforward proof. We rely heavily on the fact that the prefix is an ECF and the ECF is defined by a reduced trajectory, and all reduced trajectories terminate with an odd number.
Let us begin by considering a parent node n with prefix {p0​,p1​,…,pm​}. The corresponding ICF is as follows:
Now, suppose that this parent node has good nature 🟢, denote the number at left and right children as gL​ and gR​ respectively. The resulting ICFs are:
Note that in both bad and good cases, we have the expression pr​+1−pm​; this is always a positive integer as pm​≤pr​ by definition of how prefixes change within the PIPTree.
bR′​=2pr​+1−pm​3bL′​+1​−3m+1
gL′​=2pr​+1−pm​3gR′​+1​+3m+1
We have defined ECFs over reduced trajectories only, so prefixes should also correspond to trajectories with odd terminating numbers. As such, gL′​,gR′​ and bL′​,bR′​ should be odd numbers, if the parent is good or bad respectively.
Note that nm​ is a terminating number too, and must be odd by definition. With this, we can observe that bL′​ and gR′​ are always odd!
Now, notice that gL′​=3m+1+bR′​. So, if bR′​ is odd then gL′​ is even, or if bR′​ is even then gL′​ is odd. This means that if bR′​ is odd, the node has bad nature; or if bR′​ is even, the node has good nature.
2pr​+1−pm​3nm​+1​
If you look carefully, this is as if we are doing a reduced Collatz operationR. In fact, our node n with prefix {p0​,p1​,…,pm​} corresponded to the trajectory:
That is it! Check if bR′​ is odd, and if it is, the node is bad; otherwise good.
The nature of a node at some index i is always the same, regardless of the size of PIPTree; it is an invariant. How is that possible if we calculated the nature via number and prefix, which is changing?
To see why, consider the effects of going from PIPTree of k to PIPTree of k+1.
Although the number and prefix changed for the node in PIPTree, the terminating number did not change. Nature calculation relies on the terminating number, the root prefix pr​ and pm​ for a given node. Well, pr​ and pm​ both increased by 1, so their change canceled out too! As a result, the nature of a node does not change with respect to PIPTree size.
The root node is always good. The number is n=2pr​ with prefix {pr​}. As such, the terminating number of this trajectory is 1 (i.e. nm​=1). So: