Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a simple attempt as a proof of the Collatz Conjecture, as defined in Wikipedia. I must tell you that I'm not a math expert and I did it just for fun. Surelly it have serious flaws I just curious to know what could they be.

Introduction

The conjecture holds true if all natural numbers will make the succession to converge to 1 after a finite number of applications of the recursive function $f$, computing $n/2$ if $n$ is even, and $3n+1$ if $n$ is odd.

A useful observation

One useful observation is that if it holds true for $n \geq 2$ an even number, then must hold true for $f(n)=n/2$, since it is the next number in the succession. Analogously if it holds true for $n \geq 3$ an odd number, then it must hold true for $f(n)=3n+1$ too, since it is the next in the chain. In both cases, also the conjecture remains true for $2n$ the previous number in the chain, that is if $a_i=n$, then $f(a_{i-1})=f(2n)=a_i=n$, since $2n$ will always be even, and is in the same chain that $n$.

Proof

The Collatz conjecture holds for all natural numbers, and that the succession is finite (the convergence to reach 1 requires a finite number of steps).

I will proceed by induction on $a_0=n$, for natural $n \geq 1$.

Base case $a_0=1$: The succession goes: $a_0=1; a_1=3.1+1=4; a_2=2; a_3=1$. Also the succession converged in 3 steps.

Inductive hypothesis: The succession is finite an always converge to 1.

The inductive step is divided in two sub cases: the $n$ is even or the $n$ is odd.

Inductive case: $n \geq 2$ is an even number: This means that exist a natural number $q < n$ such that $a_0=n=2q$. Then the next number in the succession is $a_1=f(a_0)=f(2q)=2q/2=q$. As $q < n$ then by inductive hypothesis lets assume that for $q$ the succession converged in $s$ steps, then for $n$ must converge is $s+1$ steps.

Inductive case: $n \geq 3$ is an odd number: This means that the initial number in the succession is $a_0=n$, an odd number. We can construct a virtual succession by using the number $a_{-1}=2n$, which is an even number, and it is in the same chain on the succession, since $f(a_{-1})=a_0$. As shown previously, the conjecture apply for even numbers, so it holds true for the number $2n$, and therefore for $n$ since it is one step further in the succession.

share|improve this question

closed as too localized by Grigory M, lhf, Asaf Karagila, Henning Makholm, Zev Chonoles Feb 9 '12 at 2:12

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

7  
Dear Gabriel, I have not read the details of your argument, but: this being a rather famous open problem at which probably almost every mathematician in the last 50 years has taken a stab, it is rather unlikely that such a short argument would solve it! –  Mariano Suárez-Alvarez Feb 8 '12 at 5:44
5  
In your odd case, you assume the result for $2n$, which you can't do since you don't know it for $2n$; you just know it for $1,...,n-1$ by your induction hypothesis. –  Zarrax Feb 8 '12 at 5:50
5  
Numerous incorrect proofs of famous open problems is not what Math.SE is for -- voted to close as "too localized". –  Grigory M Feb 8 '12 at 7:56
1  
(+1) at @Grigory. One might assume good faith anyway and modify the question to set the focus on the question of "is my approach to the method of induction valid here? (example 3x+1-problem)". Otherwise I also would like to see the question being closed. –  Gottfried Helms Feb 8 '12 at 11:24
    
chat somewhere, anyone? some new ideas on collatz –  vzn Mar 4 '13 at 16:57

1 Answer 1

You handle the case of odd $n$ by considering instead $2n$ (which indeed has $n$ in its succession) and appealing to your even case. However, the even case is proven via strong induction. So, to prove $2n$ converges, you must know already that $n$ converges. Your logic here is circular.

Imagine how your proof would work out the convergences in order. You showed 1 converges by hand. You know 2 converges, because it is just one step away from 1, which was already shown to converge.

What about 3? You say to consider 6 instead and appeal to the even case. Your even case says divide 6 by 2 to get 3, but the convergence of 3 is precisely what we were hoping to prove in the first place.

In general, when using induction, you may only appeal to earlier cases to help you prove the later cases, not the other way around.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.