# Proof of Collatz conjecture

### Proof of Collatz conjecture

Let $x_n$ be an odd positive integer. From the sequence's formula, $x_{n+1}=\frac{(3x_n+1)}{2^k}$, $x_{n+2}=\frac{(3x_{n+1}+1)}{2^m}$, and so forth.
For there to exist a cycle in the sequence, there must exist an odd integer $x_0$ such that $x_n=x_0$
For an odd integer $x_0$, the next odd integer, $x_1$ will be given by $\frac{3x_0+1}{2^k}$. For $x_1\geq x_0, k<2$
To check whether a one step cycle exists,
\begin{align*}
\frac{3x_0+1}{2^k}&=x_0\\
2^kx_0-3x_0&=1\\
x_0&=\frac{1}{2^k-3}\\
\end{align*}
The only value of $k$ such that $x_0$ is a positive integer is 2 to give $x_0=1$. Hence, a one step cycle exists only at 1, and we note that it is the only integer such that $x_1=x_0$ where $k=2$. For any other positive odd integer, for $x_1\geq x_0$, then $k=1$. $k$ cannot be 0 because $3x_0+1$ will always be even.

The second odd integer, $x_2$ is given by
\begin{align*}
x_2&=\frac{3x_1+1}{2^m}\\
&=\frac{3(\frac{3x_0+1}{2^k})+1}{2^m}\\
&=\frac{9x_0+3+2^k}{2^{k+m}}
\end{align*}
$x_2\geq x_0$ iff $k+m<4$. This is because the we have multiplied $x_0$ by a factor of $3\times 3$ or 9, and hence we can divide the result by $2^3$ or 8 to get a whole number and not $2^4$.\\
To check whether a two step cycle exists,
\begin{align*}
\frac{9x_0+3+2^k}{2^{k+m}}&=x_0\\
2^{k+m}x_0-9x_0&=3+2^k\\
x_0&=\frac{3+2^k}{2^{k+m}-9}\\
\end{align*}
For $x_0$ to be a positive number, then $2^{k+m}>9$, which means $2^{k+m}>2^3$, a contradiction. Again, the only value that satisfies the equation is such that $x_0$ is 1 for $k=2$ and $m=2$. The equation cannot yield $x_0>1$ because $2^{k+m}>9$

The third odd integer will be given by
\begin{align*}
x_3&=\frac{3x_2+1}{2^p}\\
&=\frac{3(\frac{3x_1+1}{2^m})+1}{2^p}\\
&=\frac{3(\frac{9x_0+3+2^k}{2^{k+m}})+1}{2^p}\\
&=\frac{27x_0+9+3.2^k+2^{k+m}}{2^{k+m+p}}
\end{align*}
For any $x_0>1, x_3>x_0$ if $k+m+p<5$. This is because we multiply $x_0$ by a factor of $3\times 3\times 3$ or 27, and hence if we divide the result by $2^5$, 32, we would end up with a number less than $x_0$
We still check whether there exists an integer $x_0$ from which a three step cycle occurs.
\begin{align*}
\frac{27x_0+9+3.2^k+2^{k+m}}{2^{k+m+p}}&=x_0\\
2^{k+m+p}x_0-27x_0&=9+3.2^k+2^{k+m}\\
x_0&=\frac{9+3.2^k+2^{k+m}}{2^{k+m+p}-27}
\end{align*}
Similarly, for $x_0$ to be a positive integer, $2^{k+m+p}>27$, contradicting our earlier findings. Only one special case holds for this equation too, $x_0=1$ when $k=m=p=2$.

In general, when we check $x_0$ for an $n$ step cycle, we generate the following equation $$\frac{x_0=3^{n-1}+3^{n-2}2^{a_1}+3^{n-2}2^{a_1+a_2}+...+3.2^{a_1+a_2+a_3+...+a_{n-1}}+2^{a_1+a_2+a_3+...+a_n}}{2^{a_1+a_2+a_3+...+a_n}-3^n}$$
For any $x_0>1$, $2^{a_1+a_2+a_3+...+a_n}<3^n$ or $2^{a_1+a_2+a_3+...+a_n}<2^{2n}$ and hence, the equation cannot have any value above 1.
$x_0$ can only be 1 iff each $a_i=2$. The values of $a_i$ can be found by equating the numerator to the denominator.
This proves that no cycle exists apart from \{$4$, $2$, $1$\}.

Mariga

Posts: 7
Joined: Wed Mar 22, 2017 3:01 am
Reputation: 1

### Re: Proof of Collatz conjecture

Let $x_n$ be an odd positive integer. From the sequence’s formula, $x_{n+1}=\frac{3x_n+1}{2^k}$, $x_{n+2}=\frac{3x_{n+1}+1}{2^m}$ and so forth, $m,k\in \mathbb{Z^+}$\\
For there to exist a cycle in the sequence, there must exist an odd integer $x_0$ such that $x_n=x_0$.\\
Let $x_1$, the next odd integer after $x_0$,be given by
$$x_1=\frac{3x_0+1}{2^{a_1}}$$
$x_2$ will be given by
$$x_2=\frac{3x_1+1}{2^{a_2}}$$
$x_2$ in terms of $x_0$ will be
\begin{align*}
x_2&=\frac{3(\frac{3x_0+1}{2^{a_1}})+1}{2^{a_2}}\\
&=\frac{9x_0+3+2^{a_1}}{2^{a_1+a_2}}
\end{align*}
$x_3$ will be given by
\begin{align*}
x_3&=\frac{3x_2+1}{2^{a_3}}\\
&=\frac{3(\frac{3x_1+1}{2^{a_2}})+1}{2^{a_3}}\\
&=\frac{3(\frac{9x_0+3+2^{a_1}}{2^{a_1+a_2}})+1}{2^{a_3}}\\
&=\frac{27x_0+9+3.2^{a_1}+2^{a_1+a_2}}{2^{a_1+a_2+a_3}}
\end{align*}
From the three examples,we can generate a formula for $x_n$ in terms of $x_0$,which will be
$$x_n=\frac{3^nx_0+3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}}{2^{\sum\limits_{n=1}^na_i}}$$
Let $x_n=x_0$, hence
$$x_0=\frac{3^nx_0+3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}}{2^{\sum\limits_{n=1}^na_i}}$$
Let $\sum\limits_{n=1}^na_i$ be $k$
$$2^kx_0-3^nx_0=3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}$$
$$x_0(2^k-3^n)=3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}$$
$2^k$ can be expressed as $(2^{\frac{k}{n}})^n$
$$x_0[(2^{\frac{k}{n}})^n-3^n]=3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}\tag{1}$$
When factoring,
$$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots +a.b^{n-2}+b^{n-1})$$
This is same as
$$a^n-b^n=(a-b)(b^{n-1}+b^{n-2}a+b^{n-3}a^2+\cdots +b.a^{n-2}+a^{n-1})$$
We therefore notice the polynomial in equation (1) is regular.
Hence, $x_0[(2^{\frac{k}{n}})^n-3^n]$ can be expressed as,
$$x_0[(2^{\frac{k}{n}})^n-3^n]=x_0(2^{\frac{k}{n}}-3)(3^{n-1}+3^{n-2}2^{\frac{k}{n}}+3^{n-3}(2^{\frac{k}{n}})^2+\cdots +3(2^{\frac{k}{n}})^{n-2}+(2^{\frac{k}{n}})^{n-1})$$
$$=3^{n-1}(2^{\frac{k}{n}}-3)x_0+3^{n-2}2^{\frac{k}{n}}(2^{\frac{k}{n}}-3)x_0+3^{n-3}(2^{\frac{k}{n}})^2(2^{\frac{k}{n}}-3)x_0+\cdots +3(2^{\frac{k}{n}})^{n-2}(2^{\frac{k}{n}}-3)x_0+(2^{\frac{k}{n}})^{n-1})(2^{\frac{k}{n}}-3)x_0$$
\\
Each term in this polynomial corresponds to the terms in the polynomial in equation (1).
\begin{align*}
\end{align*}
Hence, each of these corresponding terms will be equal. Hence,
\begin{align*}
3^{n-1}&=3^{n-1}(2^{\frac{k}{n}}-3)x_0\\
1&=(2^{\frac{k}{n}}-3)x_0\\
x_0&=\frac{1}{(2^{\frac{k}{n}}-3)}\tag{2}
\end{align*}
Substituting this in the next pair of terms,
\begin{align*}
3^{n-2}2^{a_1}&=3^{n-2}2^{\frac{k}{n}}(2^{\frac{k}{n}}-3)\frac{1}{(2^{\frac{k}{n}}-3)}\\
2^{a_1}(2^{\frac{k}{n}}-3)&=2^{\frac{k}{n}}(2^{\frac{k}{n}}-3)\\
2^{a_1}&=2^{\frac{k}{n}}
\end{align*}
Substituting this in equation (2),
$$x_0=\frac{1}{(2^{a_1}-3)}$$
The only value that satisfies this equation such that $x_0$ and $a_1$ are both positive integers is $a_1=2$ to give $x_0=1$.

Mariga

Posts: 7
Joined: Wed Mar 22, 2017 3:01 am
Reputation: 1

### Re: Proof of Collatz conjecture

Each term in this polynomial corresponds to the terms in the polynomial in equation (1). Hence, each of these corresponding terms will be equal.

Unfortunately, this statement is invalid, as you seem to be equating them with the $x_0$ term. Consider the following: $2x+5x=3x+4x$. This does not imply $2x=3x$ and $5x=4x$. Therefore, your proof is incorrect.

TheUltimate123

Posts: 1
Joined: Sun Feb 25, 2018 3:53 pm
Reputation: 0