10
$\begingroup$

Collatz's Conjecture is also known as the $3n+1$ conjecture.

Well I thought since the conjecture is dealing with natural numbers so we might as well try mathematical induction and see why it doesn't work.

I will attempt to use strong induction.

Here is the base case for $(n=1)$ or $(n=2)$

We know the conjecture works for $n=1$ and $n=2$.

So lets move on to the Induction step.

Assume the conjecture holds up to a natural number $k$ and so the conjecture holds for $ \{1,2,.....,k \}$. We now need to prove that It also holds for $k+1$

Here we have two cases (1) $k$ is even (2) $k$ is odd

We start with the easier case , case (2)

If $k$ is odd then $k+1$ is even and hence the first step is division $\frac{k+1}{2}$ will be in the list $ \{1,2,..........,k \}$ because $\frac{k+1}{2} < k$ and hence we are done for this case.

However, Life couldn't be that easy :D

So we have to consider case (1)

If $k$ is even then $k+1$ is odd and so we have to multiply $3(k+1) + 1 = 3k +4$ and $3k+4$ is even because odd(3)xeven(k) + even(4) = even + even = even so we will apply the division step $\frac{3k+4}{2}$ However, It's not always true that $\frac{3k+4}{2} \leq k$ And so the induction fails

Is there anything I did wrong here or is there anything I can add to proceed even a little bit further ?

$\endgroup$
2
  • 12
    $\begingroup$ There is a reason that this is an unsolved conjecture... $\endgroup$ Apr 4, 2015 at 2:41
  • 1
    $\begingroup$ I think that if it was solvable by induction probably some would have already tried since 1937, in particular this went through the hands of Erdös. $\endgroup$ Apr 4, 2015 at 2:42

3 Answers 3

14
$\begingroup$

You didn't do anything wrong, you've just stumbled on the main reason this conjecture is so difficult. There is no way to control the growth rate of this algorithm for a given $k$. Sometimes you'll land in the region of your induction, other times you won't.

You can find some heuristic reasoning for the conjecture here, along with some more info on why it's difficult.

$\endgroup$
12
$\begingroup$

The vein of proof you're going down would work, if you could just plug in the relevant elements. In particular, the form you seem to want is:

If, for every $k>1$, eventually $k$ iterates to some $k'<k$, then we can use induction on $k$ to prove the Collatz conjecture.

However, proving the first bit after "if" is non-trivial - it is, after all, equivalent to the Collatz conjecture. Probably the primary danger of attacking problems like this is that you'll find a lot of statements which turn out to be equivalent to the Collatz conjecture upon a little bit of examination - which generally is a sign that you're just reformulating the problem, rather than making progress towards a full proof. (And the amount of time you can spend doing this is pretty much bounded only by how broad your mathematical knowledge is)

However, your vein of proof (considering numbers by parity) does yield a natural extension to get further results - in particular, we can consider the residue classes of $k$ mod $2^n$ - what you've done is to handle the case mod $2$:

  • If $k$ is even, then it iterates immediately to some $k'<k$.

  • If $k$ is odd, it increases in the next step.

However, we can, for instance, extend this to consider what $k$ is mod $4$.

  • If $k$ is $0$ or $2$ mod $4$, then it's even, and hence decreases.

  • If $k$ is $1$ mod $4$, then it goes to $3k+1$, which is divisible by $4$, hence iterates to $\frac{3k+1}4$ which is less than $k$ (for $k>1$).

  • If $k$ is $3$ mod $4$, then it goes to $3k+1$, is divisible by $2$ once, then we apply $3n+1$ again, and divide by two again. However, this increases $k$ by a factor of $\frac{9}4$ or so, so we're in trouble.

And we can keep checking mod $8$ and so on - essentially, what the above says is, "If there is a counterexample, then the smallest counterexample is congruent to $3$ mod $4$". Wikipedia elaborates a little more on this fact - however, it is easy enough to show that this approach can never eliminate every residue mod $2^n$ (in particular, one result is that $2^n-1$ always iterates to $3^n-1$ - so the factor of growth is unbounded, meaning a residue of $-1$ mod $2^n$ increases over the course of $n$ steps), hence there is some additional insight required.

$\endgroup$
0
$\begingroup$

Induction does work for the $n$th terms of convergence of the Collatz map. (It does not say anything directly about individual step counts / stopping times.)

First General Case

$a_{_n}=24n+5, 8n+1, 18n+4$

A sequence that begins with odd integer $24k+5$ or $8k+1$ converges on even integer $18k+4$.

Basis case

$1 \rightarrow 4$ and $5 \rightarrow 4$

Sequences $1$ and $5$ converge on $4$:
$1 \rightarrow 4$
$5 \rightarrow 16 \rightarrow 8 \rightarrow 4$

Hypothesis

Let

${B}$ be integers of the form $8k+1$
${C{_1}}$ be integers of the form $24k+5$
${E{_1}}$ be integers of the form $18k+4$
$i$ be $2n$ such that $n$ is the $n$th term and $n$ is $0$-indexed.

The elements of ${B}$ and ${C{_1}}$ form pairs, such that $c{_1}=3b+2$.

![enter image description here

Each element of ${E{_1}}$ is an even number, such that $e{_1}$ =$ (c{_1}-b)+i$.

For $\boldsymbol{n=k}$

$c_{1}$ is $(24*0)+5=5$, $b$ is $(8*0)+1=1$, and $i=0$
$c{_1}=3b+2$ is $5=(3*1)+2$
$e{_1} = (c{_1}-b)+i$ is $4=(5-1)+0$

Sequences $1$ and $5$ converge on $4$.

For $\boldsymbol{n=k+1}$

$c_{1}$ is $(24*1)+5=29$, $b$ is $(8*1)+1=9$, and $i=2$
$c{_1}=3b+2$ is $29=(3*9)+2$
$e{_1}=(c{_1}-b)+i$ is $22=(29-9)+2$

Sequences $29$ and $9$ converge on $22$.

For $\boldsymbol{n=k+1001}$

$c_{1}$ is $(24*1001)+5=24029, b$ is $(8*1001)+1=8009$, and $i=2002$
$c{_1}=3b+2$ is $24029=(3*8009)+2$
$e{_1}=(c{_1}-b)+i$ is $18022=(24029-8009)+2002$

Sequences $24029$ and $8009$ converge on $18022$.

Second General Case

$a_{_n}=24n+21, 4n+3, 18n+16$

A sequence that begins with odd integer $24k+21$ or $4k+3$ converges on even integer $18k+16$.

Basis case

$21 \rightarrow 16$ and $3 \rightarrow 16$

Sequences $21$ and $3$ converge on $16$:
$21 \rightarrow 64 \rightarrow 32 \rightarrow 16$
$3 \rightarrow 10 \rightarrow 5 \rightarrow 16$

Hypothesis

Let

${D}$ be integers of the form $4k+3$
${C{_2}}$ be integers of the form $24k+21$
${E{_2}}$ be integers of the form $18k+16$
$j$ be $(n+1)2$ such that $n$ is the $n$th term and $n$ is $0$-indexed.

The elements of ${D}$ and ${C{_2}}$ form pairs, such that $c{_2}=6d+3$.

enter image description here

Each element of ${E{_2}}$ is an even number, such that $e{_2} = c{_2}-(d+j)$.

For $\boldsymbol{n=k}$

$c_{2}$ is $(24*0)+21=21$, $d$ is $(4*0)+3=3$, and $j=2$
$c{_2}=6d+3$ is $21=(6*3)+3$
$e{_2} = c{_2}-(d+j)$ is $16=21-(3+2)$

Sequences $21$ and $3$ converge on $16$.

For $\boldsymbol{n=k+1}$

$c_{2}$ is $(24*1)+21=45$, $d$ is $(4*1)+3=7$, and $j=4$
$c{_2}=6d+3$ is $45=(6*7)+3$
$e{_2} = c{_2}-(d+j)$ is $34=45-(7+4)$

Sequences $45$ and $7$ converge on $34$.

For $\boldsymbol{n=k+1001}$

$c_{2}$ is $(24*1001)+21=24045$, $d$ is $(4*1001)+3=4007$, and $j=2004$
$c{_2}=6d+3$ is $24045=(6*4007)+3$
$e{_2} = c{_2}-(d+j)$ is $18034=24045-(4007+2004)$

Sequences $24045$ and $4007$ converge on $18034$.

Note

A subset of odd integers are not members of ${B}$, ${D}$, ${C{_1}}$, or ${C{_2}}$.

Let

${G}$ be integers of the form $24k+13$
${E{_3}}$ be integers of the form $72k+40$

The elements of ${G}$ are excluded from ${B}$, ${D}$, ${C{_1}}$, and ${C{_2}}$.

There is a union $f(G \cup {E{_3}})$ such that ${e{_3}}=(g*3)+1$.

If $g=13$, $e{_3}=40$
If $g=37$, $e{_3}=112$
If $g=5989$, $e{_3}=17968$

Elements $e{_3}$ are also of the form $18k+4$: ${E{_3}} \subseteq E{_1}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .