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)

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$.

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.