# Tangential proof regarding the Collatz Conjecture formula.

Let us start with the list: $\{1\}$.

Every iteration replace every element $x$ in the list with two elements $2x$ and $\frac {x-1}{3}$.

Conjecture: The sum of every element of the set formed by the $N$th iteration is $2^N$.

Also, as a lesser corollary:

Corollary: The number of elements in the $N$th iteration is $2^N$.

I was just messing around with reversal of the Collatz Conjecture and adding together these sets and it kept occurring. I did it for the first 20-30 iterations and it seems to be a valid conjecture. I just don't know how to prove it. Can anyone demonstrate a simple proof showing why this is true? I don't want anything too advanced. I know the basic concepts of number theory/algebraic number theory/modular arithmetic but not much beyond that.

(Please don't tell me this is somehow equivalent to the Collatz Conjecture)

The third iteration gives you the set $$\left\{-\frac23, -\frac49, -\frac13, -\frac29, 0, \frac23, 1, 8\right\},$$ which has $8$ elements, and yes, the sum of the elements is also $8$.
Now, note that $$2 \cdot 0 = 0 \text{ and } \frac{1-1}{3} = 0,$$ and similarly $$2 \cdot \left(-\frac29\right) = -\frac49 \text{ and } \frac{-\frac13 - 1}{3} = -\frac49.$$ Because of this, the fourth iteration becomes $$\left\{-\frac43, -\frac89, -\frac23, -\frac59, -\frac{13}{27}, -\frac49, -\frac{11}{27}, -\frac13, -\frac19, 0, \frac43, 2, \frac73, 16\right\},$$ which has $14$ elements and their sum is $148/9$.
• Perhaps the OP is counting elements in a multi-set, with multiplicity, so that the fourth iterate has two $0$'s and two $-4/9$'s. (If so, the question should be edited to say so.) Jul 9, 2017 at 19:18
• @BarryCipra In that case, the second corollary would be trivial, though. The first one could then be proven by induction. If $\sum_{i=1}^{2^N}x_i = 2^N$, then $$\sum_{i=1}^{2^N} 2x_i = 2\sum_{i=1}^{2^N} x_i = 2 \cdot 2^N = 2^{N+1}$$ and $$\sum_{i=1}^{2^N} \frac{x_i-1}{3} = \frac{1}{3}\left(\sum_{i=1}^{2^N}x_i - \sum_{i=1}^{2^N}1\right) = \frac{1}{3}\left(2^N - 2^N\right) = 0,$$ hence the total sum is $2^{N+1}$. Jul 9, 2017 at 20:01