Yet another proof of the Collatz conjecture

Yet another proof of the Collatz conjecture

Postby rivasjc » Sat Nov 11, 2017 8:30 am

Maybe a good one, sorry for bothering

The Collatz conjecture as stated in Wikipedia says that if we define the following function over the natural numbers;


\begin{equation}
f(n)= \left \{
\begin{split}
n/2 &\text{ if } n \equiv 0 \pmod{2}\\
3n+1 &\text{ if } n\equiv 1 \pmod{2}
\end{split}
\right .
\end{equation}

And build a sequence, starting in any arbitrary natural number as follows:

\begin{equation}
a_i= \left \{
\begin{split}
n &\text{ for } i=0\\
f(a_{i-1}) &\text{ for } i>0
\end{split}
\right .
\end{equation}

that is: $a_i$ is the value of $f$ applied to $n$ recursively $i$ times; $a_i = f^{(i}(n)$.

The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.

Now, let be $a_j$ an arbitrary number in a sequence built with the specified method. If $a_j$ is an odd number, then $a_{j+1}$ will be even. On the other hand, if $a_j$ is even, then $a_{j+1}$ can be even with a probability $1/2$, $a_{j+2}$ with a probability $1/4$ and so on.

Now let's build the sequence $b_i$ of odd numbers that results of applying function f. Assuming we start with an odd number, and after i iterations we will obtain:

\begin{equation}
b_i= (f_{odd}^{(i}f_{even}^{(\sum_{j=1}^ik(j)})(n)
\end{equation}

Where to obtain each odd element of the sequence from the previous one we had to compose the odd part of f which is $3n+1$ once and the even part of f or $n/2$ at least once.


Now, to prove the Collatz conjecture it is enough proving that the limit when $i\longrightarrow\infty$ is one or lower.

This can be done if we see that:

\begin{equation}
\lim_{i \to \infty} b_i = \lim_{i \to \infty} (f_{odd}^{(i}f_{even}^{(\sum_{j=1}^ik(j)})(n) =
\lim_{i \to \infty} (f_{odd}^{(i}f_{even}^{(i<k>})(n)
\end{equation}

And $<k>=2$ is the average value of $k(i)$, therefore after some algebra:

\begin{equation}
\lim_{i \to \infty} a_i =\lim_{i \to \infty} b_i =
\lim_{i \to \infty} \left (\frac{3^in}{4^i}+ \sum_{j=1}^i {\frac{1}{4^j}} \right ) =\frac{1}{3}
\end{equation}

But the lowest number we can reach with function f is one, and therefore that is the limit of the sequence.





rivasjc
 
Posts: 3
Joined: Sat Nov 11, 2017 8:15 am
Reputation: 0

Re: Yet another proof of the Collatz conjecture

Postby rivasjc » Mon Nov 13, 2017 2:01 am

I am sorry, the last equation is incorrect, the correct equation is the following:

\begin{equation}
\lim_{i \to \infty} a_i =\lim_{i \to \infty} b_i =
\lim_{i \to \infty} \left (\frac{3^in}{4^i}+ \sum_{j=1}^i {\frac{3^{j-1}}{4^j}} \right ) =1
\end{equation}

rivasjc
 
Posts: 3
Joined: Sat Nov 11, 2017 8:15 am
Reputation: 0

Re: Yet another proof of the Collatz conjecture

Postby rivasjc » Mon Nov 13, 2017 2:46 pm

Rewritten

The Collatz conjecture as stated in Wikipedia says that if we define the following function over the natural numbers:


\begin{equation}
f(n)= \left \{
\begin{split}
n/2 &\text{ if } n \equiv 0 \pmod{2}\\
3n+1 &\text{ if } n\equiv 1 \pmod{2}
\end{split}
\right .
\end{equation}

And build a sequence, starting in any arbitrary natural number as follows:

\begin{equation}
a_i= \left \{
\begin{split}
n &\text{ for } i=0\\
f(a_{i-1}) &\text{ for } i>0
\end{split}
\right .
\end{equation}

that is: $a_i$ is the value of $f$ applied to $n$ recursively $i$ times; $a_i = f^{(i}(n)$.

The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.

Let be $a_j$ an arbitrary number in a sequence built with the specified method. If $a_j$ is an odd number, then $a_{j+1}$ will be even. On the other hand, if $a_j$ is even, then $a_{j+1}$ can be even with a probability $1/2$, $a_{j+2}$ with a probability $1/4$ and so on.

Now let's build the sequence $b_i$ of odd numbers that results of applying function f. Assuming we start with an odd number, and after i iterations we will obtain:

\begin{equation}
b_i= f_{even}^{k(i)}(f_{odd}(f_{even}^{k(i-1)}(f_{odd}(...f_{even}^{k(1)}(f_{odd}(n))))))
\end{equation}

Where to obtain each odd element of the sequence from the previous one we had to compose the odd part of f which is $3n+1$ once and the even part of f or $n/2$ at least once. The resulting term is:

\begin{equation}
b_i = \frac{3^in}{2^{\sum_{j=1}^ik(j)}}+ \sum_{j=1}^i {\frac{3^{j-1}}{2^{\sum_{j=1}^ik(j)}}}
\end{equation}

Thus, we obtain, for high values of i:



\begin{equation}
\lim_{i \to \infty} b_i = \lim_{i \to \infty} \left (\frac{3^in}{2^{i<k>}}+ \sum_{j=1}^i {\frac{3^{j-1}}{2^{i<k>}}} \right )
\end{equation}

And $<k>=2$ is the average value of $k(i)$, therefore after some algebra:

\begin{equation}
\lim_{i \to \infty} a_i =\lim_{i \to \infty} b_i =
\lim_{i \to \infty} \left (\frac{3^in}{4^i}+ \sum_{j=1}^i {\frac{3^{j-1}}{4^j}} \right ) =1
\end{equation}

rivasjc
 
Posts: 3
Joined: Sat Nov 11, 2017 8:15 am
Reputation: 0


Return to Number Theory



Who is online

Users browsing this forum: No registered users and 1 guest