Where's the flaw in this proof of the Collatz Conjecture?

[raycb]

The conjecture states that:

Given a positive integer n,

If n is even then divide by 2.

If n is odd then multiply by 3 and add 1

Conjecture: by repeating these operations you will eventually reach 1.



Proof:



Let n be the smallest positive integer that is a counterexample to the conjecture.

If n is even then it can be divided by two to give a smaller number, leading to a contradiction.

Assume n = 4k + 1.

Multiply it by 3, add 1, and divide by 2 twice.

The result is 3k + 1, a number smaller than n, leading to a contradiction. Therefore n has the form

n = 4k - 1.

Multiply by 3, add 1, and divide by 2.

The result is 6k - 1. If k is odd, then 6k - 1 is one more than a multiple of 4, which is impossible, therefore k is even, and n has the form

n = 8k - 1

Multiply by 3, add 1, and divide by 2.

The result is 12k -1, with k necessarily even. In this manner it can be proved that n must have the form 16k - 1, 32k -1, 64k -1, and so on, requiring n to be infinitely large, which is impossible.

 

[Infrared]

The result is 12k -1, with k necessarily even.

Why must this k necessarily be even? Keep in mind that you are using the same letter k for two different quantities when you write n=4k-1 and n=8k-1 so showing that k is even in the first expression does not mean that the second k is.

 

[raycb]

Well, I'm trying to say that n has the form of a number with a remainder of -1 for some power of 2.

The number 12k - 1 can be written as 8k + 4k -1, and the number has to have a remainder of -1 mod 8, therefore 4k is a multiple of 8, and k is even. My argument is that these operations always require k to be even, that there is a repeating pattern. All I can do is post it and see how others see it.

 

[Infrared]

Ok, I see your argument now. Can you explain your n=4k-1 case? You conclude that n=6k-1 and that k can not be odd because it would be one more than a multiple of 4. However, you only showed that the smallest counterexample could not have this form but 6k-1>4k-1=n, where n is the smallest counterexample so I don't see the problem.

 

[raycb]

I'm attacking the problem in two different ways:

One, by proving that a number is reached that is smaller than n; two, by proving that n must have a remainder of -1 for a still higher power of 2.

The fact that 6k -1 > 4k -1 doesn't apply here. Once it is proven that k is even in 6k -1, then n not only has the form 4k -1, but it necessarily has the form 8k - 1.

 

[Infrared]

I'm attacking the problem in two different ways:

One, by proving that a number is reached that is smaller than n; two, by proving that n must have a remainder of -1 for a still higher power of 2.

The fact that 6k -1 > 4k -1 doesn't apply here. Once it is proven that k is even in 6k -1, then n not only has the form 4k -1, but it necessarily has the form 8k - 1.

And I'm disputing that the k in 6k-1 must be even. It doesn't matter whether 6k-1 is a one more than a multiple of four or not since it would not be the smallest counterexample even if it was (4k-1 would be).