Where is the flaw in this "proof" of the Collatz Conjecture?

Question

Edit

I've highlighted the area in the proof where the mistake was made, for the benefit of anyone stumbling upon this in the future. It's the same mistake, made in two places:

This has proven the Collatz Conjecture for all even numbers

The Collatz Conjecture was shown to hold for $N+1$ when $N+1$ is even -- it was never shown to hold for all even numbers -- just that one, lone even number.

[The Collatz Conjecture holds for] all odd numbers for which $N-1$ is a multiple of $4$

The same as above: it was shown that the Collatz Conjecture holds for $N+1$ if $N+1$ is of the form $4k+1$. It was never shown to hold for all numbers of this form -- just that one, lone number.

In order for my proof to be valid, I would need to prove that the Collatz Conjecture holds for $N+1+4j = 4k+1$ (every fourth number after $N+1$) for, at a minimum, $N+1+4j < 1.5N+2$

Original Post

I spent about an hour thinking about the Collatz Conjecture and stumbled upon what feels like a proof... but I came to it all too easily to have done everything right.

1. the obvious that everyone has already figured out:

Assume the Collatz Conjecture holds for all numbers $1...N$

We can trivially prove the Collatz Conjecture for some base cases of $1,$ $2,$ $3,$ and $4$. This is sufficient to go forward.

2. Yet more obvious:

1. If $N$ is odd, $N+1$ is even
2. $(N+1)/2 < N$ for $N > 3$
3. By the induction hypothesis, the Collatz Conjecture holds for $N+1$ when $N+1 = 2k$

3. Now the last obvious bit:

1. If $N$ is even, $N+1$ is odd
2. If $N+1$ is odd, the next number in the series is 3(N+1)+1
3. Since $(N+1)$ is odd, $3(N+1)+1$ is even
4. The next next number in the series is $(3(N+1)+1)/2$
5. This simplifies to: $(3N + 4)/2 = 1.5N + 2$

4. Now the first tricky bit:

1. If $N$ is a multiple of $4$:
2. $1.5N$ is a multiple of $6$, and therefore even. $1.5N + 2$ is therefore even
3. The next next next number in the series is therefore $(1.5N+2)/2$
4. This simplifies to $0.75N + 1$
5. This is less than $N$ for $N > 4$
6. By the induction hypothesis, the Collatz Conjecture holds for $N+1$ when $N+1 = 4k + 1$

This has proven the Collatz Conjecture for all even numbers and all odd numbers for which $N-1$ is a multiple of $4$... Now to blow your minds:

5. Breaking out of formal equations into patterns and such since I didn't know how to formalize this bit with math symbols:

1. We now know that a number $N+1$ can ONLY violate the Collatz Conjecture if $N$ is even and not a multiple of $4$. In other words, the only way a number could potentially violate the Collatz Conjecture is if it's of the form $N+1 = 4k - 1$
2. This limits our numbers to test to 2+1, 6+1, 10+1, 14+1, 18+1, 22+1, etc. (note that I wrote these numbers in "$N+1$" format so it'd be simpler to apply the $1.5N+2$ shortcut)
3. We'll apply our $1.5N + 2$ shortcut to a handful of these numbers:

2  -> 3+2  = 5  (4 +1) -- 4 is a multiple of 4 (duh)
6  -> 9+2  = 11 (10+1)
10 -> 15+2 = 17 (16+1) -- 16 is a multiple of 4
14 -> 21+2 = 23 (22+1)
18 -> 27+2 = 29 (28+1) -- 28 is a multiple of 4
22 -> 33+2 = 35 (34+1)
26 -> 39+2 = 41 (40+1) -- 40 is a multiple of 4
30 -> 45+2 = 47 (46+1)
34 -> 51+2 = 53 (52+1) -- 52 is a multiple of 4
38 -> 57+2 = 59 (58+1)
42 -> 63+2 = 65 (64+1) -- 64 is a multiple of 4
46 -> 69+2 = 71 (70+1)

4. Every other line we automatically know the Collatz Conjecture will hold, because we've hit a number that can be expressed as $4k+1$
5. Looking at the "kept" rows, we can see that all we need to test now are numbers of the form: N+1 = 8k - 1 (in other words, the rows where N = 8k - 2 -- 6, 14, 22, etc.)

6. And finally, recurse on this solution by drawing a new table and instead of computing the "next next" value, compute the "next next next next" value:

"Next next next" value = 3(1.5N + 2) + 1 = 4.5N + 7

"next^4" value is half of this -- 2.25N + 3.5

6  -> 27 +7 = 34  -> 17  (16 +1) -- 16 is a multiple of 4
14 -> 63 +7 = 70  -> 35  (34 +1)
22 -> 99 +7 = 106 -> 53  (52 +1) -- 52 is a multiple of 4
30 -> 135+7 = 142 -> 71  (70 +1)
38 -> 171+7 = 178 -> 89  (88 +1) -- 88 is a multiple of 4
46 -> 207+7 = 214 -> 107 (106+1)
54 -> 243+7 = 250 -> 125 (124+1) -- 124 is a multiple of 4
62 -> 279+7 = 286 -> 143 (142+1)

Every other line we automatically know the Collatz Conjecture will hold, because we've hit a number that can be expressed as 4k+1

We now know a number can only violate the Collatz Conjecture if it's of the form: N+1 = 16k - 1... Recurse again:

"next^5" value is 3(2.25N + 3.5) + 1 = 6.75N + 11.5

"next^6" value is (6.75N + 11.5)/2 = 3.375N + 5.75

14   -> 53  = 52  + 1 -- 52 is a multiple of 4
30   -> 107 = 106 + 1
46   -> 161 = 160 + 1 -- 160 is a multiple of 4
62   -> 215 = 214 + 1
78   -> 269 = 268 + 1 -- 268 is a multiple of 4
94   -> 323 = 322 + 1
110  -> 377 = 376 + 1 -- 376 is a multiple of 4
126  -> 431 = 430 + 1

We now know a number can only violate the Collatz Conjecture if it's of the form N+1 = 32k - 1

At this point, a pattern is quickly emerging:

1. First, a number could only violate the Collatz Conjecture if it was of the form N+1 = 4k - 1
2. Next, a number was shown that it could only violate the Collatz Conjecture if it was of the form N+1 = 8k - 1
3. Next, a number was shown that it could only violate the Collatz Conjecture if it is of the form N+1 = 16k - 1
4. Now, a number has been shown that it can only violate the Collatz Conjecture if it is of the form N+1 = 32k - 1

I've continued this process (recursively building this table and removing rows that I know cannot violate the Collatz Conjecture since they can be expressed as 4k+1) all the way up until 512k - 1 by hand.

I do not know how to formalize this final process in mathematical notation, but I believe it demonstrates at least a viable method for proving the Collatz Conjecture. For every two steps we take into the Collatz series, we increase the power on our definition of "only numbers that could possibly violate the conjecture". Therefore for an arbitrarily large power we know that the conjecture will still hold.

For Fun

To help me in building these tables, I crafted the following Python script:

# Increment this variable to recurse one level deeper
test = 1

### No need to edit below here, but feel free to read it ###
depth = 2 * test
step = 2 ** (test + 1)
start = step - 1

for x in range(0, 20):
    num = start + x * step
    _num = num
    _depth = depth
    while _depth > 0:
        if _num % 2 == 0:
            _num = _num / 2
        else:
            _num = 3 * _num + 1
        _depth -= 1
    text = ""
    if (_num - 1) % 4 == 0:
        text = "-- multiple of 4"
    print "%s: %s = %s + 1 %s" % (num - 1, _num, _num - 1, text)

Answer 1

There is a subtle issue with your induction argument: you are assuming that the Collatz conjecture holds for all integers $\leq n$, and then want to prove it holds for $n+1$ (strong induction). So far, so good.

You then prove that for some cases ($n+1$ even, or of the form $4k+1$) that the Collatz conjecture holds by the inductive hypothesis. Fine.

You then try to argue that for some numbers of the form $4k+3$, you eventually hit a number of the form $4k+1$, so that the Collatz conjecture holds... not so fast. You haven't proven that the Collatz conjecture holds for all integers of the form $4k+1$. You've proven it's true for $n+1$, if $n+1$ happens to be of that form, and you've assumed it's true for all numbers of that form $\leq n$ (by the inductive hypothesis) but you haven't shown that Collatz holds for numbers of the form $4k+1$ that are larger than $n+1$.

Answer 2

The error is:

We now know that a number $N+1$ can ONLY violate the Collatz Conjecture if $N$ is even and not a multiple of $4$.

We don't know that. What we know is that if there are numbers that violate the Collatz conjecture, then the smallest such number is $1$ more than something even and not a multiple of $4$. But there may be larger counterexamples which don't look like that.

This is how proof by induction works: if there's a counterexample, there must be a smallest counterexample, i.e. the conjecture is false for some number $n+1$ but true for all numbers $\leq n$. Then we can try to show that this can't happen. But if we can't deduce a contradiction from this, but only get some conditions which $n+1$ has to satisfy, then these conditions only hold for the smallest counterexample, not for every counterexample, since we had to assume that $n+1$ was the smallest counterexample in order to make the deduction.

Answer 3

In addition to the previous comments, there is another implicit assumption that needs to be addressed for this proof to work: The consideration for other loops.

The danger of this flaw is evident here: I used your method outlined in your proof, assuming $4k+1$ defines the numbers that converge to 1 and thus prove the Collatz Conjecture. I extended this formula to the modified Collatz rule $3x+5$, since the only difference is the $+5$ instead of $+1$. (I refrained from using $3x+3$ because its structure is completely different from that of $3x+1$ and $3x+5$.)

To achieve this, I used $4k+5$ for appropriateness, since the $n/2$ rule still applies for $3x+5$. I then look at the following sequence generated:

9,17,21,25,29,...

Immediately trouble unfolds. 9 goes to 32, which goes to 1, which completes the 8-4-2-1 loop.

13 goes to 11, which goes to 38, which then finds itself in the 19 loop. [19-62-31-98-49-152-76-38-19]

17 goes to 7, which goes to 13. 21 goes to 17 which goes to 7... maybe there is a pattern here?

25... ruins the entire new pattern. It goes to 80, which is a straight shot to the 5 loop [20-10-5-20].

And 29? Dead center of the 23 loop. [29-92-46-23-74-37-116-58-29].

Therefore, tuning this proof to prove that $3x+1$ will not wander to infinity is completely possible, however assuming every number reaches a power of 2 at some point may lead to further trouble. Especially since a sequence wandering to infinity for the Collatz Conjecture must never reach a power of 2 as $5x+1$ seems to demonstrate with its seemingly infinite 7 sequence.