# 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: 0

### 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: 0