Trying mathematical induction with $3n+1$ conjecture

Question

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 ?

Answer 1

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.

Answer 2

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.