Proof of Collatz conjecture

Proof of Collatz conjecture

Postby Mariga » Fri Apr 28, 2017 6:09 am

Let [tex]x_n[/tex] be an odd positive integer. From the sequence's formula, [tex]x_{n+1}=\frac{(3x_n+1)}{2^k}[/tex], [tex]x_{n+2}=\frac{(3x_{n+1}+1)}{2^m}[/tex], and so forth.
For there to exist a cycle in the sequence, there must exist an odd integer [tex]x_0[/tex] such that [tex]x_n=x_0[/tex]
For an odd integer [tex]x_0[/tex], the next odd integer, [tex]x_1[/tex] will be given by [tex]\frac{3x_0+1}{2^k}[/tex]. For [tex]x_1\geq x_0, k<2[/tex]
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, [tex]x_2[/tex] 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 [tex]x_0[/tex] to be a positive number, then [tex]2^{k+m}>9[/tex], which means [tex]2^{k+m}>2^3[/tex], a contradiction. Again, the only value that satisfies the equation is such that [tex]x_0[/tex] is 1 for $k=2$ and $m=2$. The equation cannot yield [tex]x_0>1[/tex] because [tex]2^{k+m}>9[/tex]

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 [tex]x_0>1, x_3>x_0[/tex] if [tex]k+m+p<5[/tex]. This is because we multiply [tex]x_0[/tex] by a factor of [tex]3\times 3\times 3[/tex] or 27, and hence if we divide the result by $2^5$, 32, we would end up with a number less than [tex]x_0[/tex]
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 [tex]x_0[/tex] to be a positive integer, [tex]2^{k+m+p}>27[/tex], contradicting our earlier findings. Only one special case holds for this equation too, [tex]x_0=1[/tex] when [tex]k=m=p=2[/tex].

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 [tex]x_0>1[/tex], [tex]2^{a_1+a_2+a_3+...+a_n}<3^n[/tex] or [tex]2^{a_1+a_2+a_3+...+a_n}<2^{2n}[/tex] and hence, the equation cannot have any value above 1.
[tex]x_0[/tex] can only be 1 iff each [tex]a_i=2[/tex]. The values of [tex]a_i[/tex] 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

Postby Mariga » Thu May 11, 2017 1:29 pm

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*}
3^{n-1}\quad &:\quad 3^{n-1}(2^{\frac{k}{n}}-3)x_0\\
3^{n-2}2^{a_1}\quad &:\quad 3^{n-2}2^{\frac{k}{n}}(2^{\frac{k}{n}}-3)x_0\\
3^{n-3}2^{a_1+a_2}\quad &:\quad 3^{n-3}(2^{\frac{k}{n}})^2(2^{\frac{k}{n}}-3)x_0\\
\vdots\qquad &:\qquad \vdots \\
3.2^{\sum\limits_{n=1}^{n-2}a_i}\quad &:\quad 3(2^{\frac{k}{n}})^{n-2}(2^{\frac{k}{n}}-3)x_0\\
2^{\sum\limits_{n=1}^{n-1}a_i}\quad &:\quad (2^{\frac{k}{n}})^{n-1})(2^{\frac{k}{n}}-3)x_0
\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


Return to Number Theory



Who is online

Users browsing this forum: No registered users and 1 guest