The Collatz Conjecture

So, I think I figured out the Collatz Conjecture proof, but I'm not sure if there is anything wrong in my proof. Please tell me if you find it.. :D

First, we have to know what is Collatz Conjecture. Collatz Conjecture is a sequence conjecture that is defined as follows:

We start with a positive integer $n$. If $n$ is even, then divide it by 2. If $n$ is odd, then multiply it by 3 and then add it with 1. Then we repeat this with the remaining term. The conjecture is for all positive integers, this sequence will reach 1.

For example, let's pick 3 for our first number, then the sequence is:

• 3 is odd, so the next term is $3 \times 3$ $+1$ = $10$
• 10 is even, so the next term is $\frac{10}{2}$ = $5$
• 5 is odd, so the next term is $3 \times 5$ $+1$ = 16
• 16 is even and it is a power of 2 ( $2^{4}$ ), so all the next term is 8, 4, 2, and 1

Now here is my proof (please tell me if something's wrong).

Based on the definition of the conjecture, the domain is sets of all positive integers. We can divide the positive integers into two types, the odd positive integers ( like 1, 7, and 131 ), and the even positive integers ( like 2, 10, and 324 ). The even positive integers can be divided again into two types, the even positive integers that are powers of 2 ( like 8, 32, and 512 ), and the even positive integers that are not powers of 2 ( like 20, 98, and 1002 ).

First, we start at a positive integer $n$. The first case is that $n$ is even, and the second case is that $n$ is odd.

• Case 1 : $n$ is even (powers of 2)

Because powers of 2 has the term $2^{m}$, we can conclude that all powers of two will always reach 1.

If $n$ = $2^{m}$, then $\frac{n}{2^{m}}$ = $1$

By dividing a power of two $2^{m}$ with two $m$ times, we will reach 1.

The even positive integers that is not powers of 2 means that the integers have at least 1 odd prime factor. For example, 20 is not a power of 2 because it has an odd prime factor (that is 5) , and 42 is not a power of 2 because it has 2 odd prime factor (that is 3 and 7). So, if we divide these type of positive integers by 2 repeatedly, we will eventually reach an odd number. That means if we can prove that all odd number will reach 1, then we simultaneously prove that all even integers that is not powers of 2 will also reach 1.

• Case 2 : $n$ is odd

Let's see the function term of this conjecture.

$f(n)$ = $\frac{n}{2}$ if $n$ is divisible by 2, and $f(n)$ = $3n + 1$ if $n$ is not divisible by 2.

The term $3n + 1$ is always even for all odd integers, because for all odd integers $n$, $3n$ is always odd. An odd number added with odd number will produce an even integer. So, $3n + 1$ is always even for all odd positive integers. This means there's no even-odd-odd pattern in a Collatz sequence. Now consider these terms when $n$ is odd.

$n$ -- $3n + 1$ -- $\frac{3n + 1}{2}$

Note that there will always be $\frac{3n + 1}{2}$ after $3n + 1$ because $3n + 1$ is always even. Now we are going to use the term loop to define whether a sequence will have a number that appears more than 1 time.

For instance, on a Collatz conjecture, the sequence

4, 2, 1, 4, 2, 1

has a loop. If there's a loop on a Collatz sequence before we reach 1, then this conjecture is false.

So, where do we start? Well, we can look at the odd-even-odd term above. We can check if there is a positive integer $n$ that satisfies the third term is equal to the first term.

$n$ = $\frac{3n + 1}{2}$

$2n$ = $3n + 1$

$n$ = $-1$

But here, $n$ can't be negative. Note that two consecutive numbers on a sequence can't be the same, since there is no even integer that is also odd integer (don't try to use infinity either). So, let's continue the terms above.

$n$ -- $3n + 1$ -- $\frac{3n+1}{2}$ -- $\frac{9n+5}{2}$ -- $\frac{9n+5}{4}$

(this time, we use the odd-even-odd-even-odd pattern).

Now let's check if there is a positive integer $n$ that satisfies the fifth term is equal to the first term.

$n$ = $\frac{9n+5}{4}$

$4n$ = $9n+5$

$n$ = $-1$

We get the answer $n$ = $-1$ again. Actually, if you continue the terms and then check if there's a number that satisfies the (2n - 1)th term is equal to the first term, you will always get the answer $n$ = $-1$.

Why? Well, let's set the odd terms of the terms above into a sequence.

$U[1]$ = $\frac{3n + 1}{2}$

$U[2]$ = $\frac{9n + 5}{4}$

$U[3]$ = $\frac{27n + 19}{8}$ (you can check it for yourself)

From this, we can conclude that

$U[a]$ = $\frac{ 3^{a}n + 3^{a} - 2^{a}}{2^{a}}$

From this, we can set the term $U[0]$ = $n$

Now we can check if there is a positive integer $n$ that satisfies the a-th term is equal to the first term.

$U[a]$ = $U[0]$

$\frac{ 3^{a}n + 3^{a} - 2^{a}}{2^{a}}$ = $n$

$3^{a}n + 3^{a} - 2^{a}$ = $2^{a}n$

$3^{a}n + 3^{a}$ = $2^{a}n + 2^{a}$

$3^{a} \times (n + 1)$ = $2^{a} \times (n + 1)$

We cancel out the $(n + 1)$ term.

$3^{a}$ = $2^{a}$

The number $a$ that satisfies this equation is $a$ = $0$.

So, $U[0]$ = $U[0]$, but this is always true. This means there is no positive integer $a$ such that $U[a]$ = $n$. In other words, there will be no numbers that will appear more than 1 time, or there will be no loop in all Collatz sequences.

So, all odd positive integers will always reach 1.

Now that we have prove that all odd positive integers will always reach 1, we simultaneously prove that all even positive integers that are not powers of 2 will also always reach 1.

Thus, all positive integers (odd integers, even integers that are powers of 2, and even integers that are not powers of 2) will always reach 1 ( Proven ).

So that's my proof of Collatz Conjecture. If there's something wrong, please tell me. Thanks :D