2
$\begingroup$

For this problem, which I believe is still unsolved, I was wondering what is wrong with this proof I thought of (probably is wrong somehow)

https://en.wikipedia.org/wiki/Collatz_conjecture

So my proof has 2 sub proofs. The first sub proof proves that all even numbers work. The second sub proof shows all odd numbers work. I am going to handwave somewhat, but it goes like this.

Sub proof 1:

The base case works for 1. Then the induction hypothesis is assume it works for all numbers going from 1 to n, where n is an odd number. Now for n+1, which is even number, the conjecture says that you have to divide by two. So (n+1)/2 is clearly within 1 to n. Therefore by the hypothesis, (n+1)/2 will work. So n+1 works. So this proves that all even numbers definitely works for the conjecture.

Sub proof 2:

The second sub proof uses the fact proved from the first sub proof. So now, in this sub proof, take any odd number $t$ > 0, by the conjecture, you have to multiply it by 3 and add 1. The result of that, call it $r$, is an even number always. So by the result of the first proof, $r$ works with the conjecture since its even. So that means $t$ will work.

So by both the sub proofs, that shows all even and odd numbers > 0 will work for the conjecture.

This seems pretty logical to me, but feels too easy to be the actual answer.

Does anyone know?

Thanks

$\endgroup$
  • 3
    $\begingroup$ This is just a circle. To prove the even case, you assume it's true for all (lesser) odd numbers. Then to prove the odd case you simply use the even case. $\endgroup$ – lulu Apr 21 '16 at 20:01
  • $\begingroup$ Can you explain more, I don't fully understand. $\endgroup$ – omega Apr 21 '16 at 20:07
  • 2
    $\begingroup$ The induction hypothesis you need for part I is that, for $n$ odd you know the claim for $1,2,\cdots, n$. But you never establish that this hypothesis can move to the next odd number, hence your proof of the first part is incomplete, and therefore your proof of the second part has no content. $\endgroup$ – lulu Apr 21 '16 at 20:13
  • 2
    $\begingroup$ To get a sense of the logical error: try to state your induction hypothesis precisely. Then show where you prove you can increase the relevant index. $\endgroup$ – lulu Apr 21 '16 at 20:15
  • $\begingroup$ " So (n+1)/2 is clearly within 1 to n. Therefore by the hypothesis, (n+1)/2 will work. " Not if (n+1)/2 is even. And if t is odd then 3t + 1 = r is even and r/2 = 1.5t + 1/2 > t. so this is not part of your induction hypotheses as your induction hypothesis was only to assume up to t. $\endgroup$ – fleablood Apr 21 '16 at 20:32
5
$\begingroup$

This doesn't work. In subproof 1, you are proving by strong induction that every even number works. This means that your induction hypothesis is only that all smaller even numbers work. Since $\frac{n+1}{2}$ may not be even, you cannot conclude that $n+1$ works.

Alternatively, you could try to combine your two subproofs into a single proof by strong induction that all numbers work. In this case, your induction hypothesis is that all numbers from $1$ to $n$ work. You then split into two cases. First, if $n$ is odd, then your subproof 1 shows that $n+1$ works. However, in the second case that $n$ is even, you can't use subproof 2, because $3n+1$ is not between $1$ and $n$ so you don't know that it works yet.

$\endgroup$
  • $\begingroup$ I think the induction hypothesis for part 1 included the odd numbers less than $n+1$ as well as the even numbers. The proof is still wrong, because there's no justification within part 1 for using that hypothesis. $\endgroup$ – David K Apr 21 '16 at 20:24
  • $\begingroup$ Right, that is the interpretation of the argument I addressed in the second paragraph. $\endgroup$ – Eric Wofsey Apr 21 '16 at 20:26
  • 1
    $\begingroup$ I think what the "proof" attempted to do was to keep the subproofs separate but use the combined induction hypothesis in the first subproof; a kind of mix-and-match of bits of your first paragraph with bits of the second. Of course that is not a legitimate method. $\endgroup$ – David K Apr 21 '16 at 20:34
  • $\begingroup$ The proof shows that if it is true for odd n, then it must be true for even n+1 and I guess the OP is assume that if n => n+1 then induction has been shown. But it hasn't, because this isn't an inductive repeatable conclusion. We will not be able to apply it to n+1 and conclude n+2. We proved n+1 by showing (n+1)/2 is an integer. We can not do the same for (n+2). Induction doesn't just fail; it was never invoked. $\endgroup$ – fleablood Apr 21 '16 at 21:56
  • $\begingroup$ " Since n+1/2 may not be even, you cannot conclude that n+1 works." since n+1/2 < n this will be true for n+1/2 odd. If n+1/2 even we do the same argument for n+1/4 and so on. So if it is true for all odd up to n,, then yes, it is true for n+1. But that is not an inductive statement. It will not follow that it is true for n+2. $\endgroup$ – fleablood Apr 21 '16 at 22:00
2
$\begingroup$

It should be clear that this proof by induction is invalid as you never actually do any induction at all.

You start with assuming it is true for odd n but never show n + 2 follows. You show that n + 1 follows but only because it is specifically even. You never show that n+1 follows by induction. As your assumption is about odd numbers it's not enough to show n + 1 is coincidentally true because it is even; you MUST show that the next odd number is nescessarily true AS A CONSEQUENCE THAT n IS TRUE. You can't and you didn't.

Sub proof 1: " Then the induction hypothesis is assume it works for all numbers going from 1 to n, where n is an odd number." up to n. ... "So n+1 works. So this proves that all even numbers definitely works for the conjecture." No. You only assumed it was true for odd numbers up to n, so this only shows it it true for even numbers up to n+1. Definitely not all even numbers. (Actually, if we assume it is true for all odd up to n, we can assume it is true for all numbers up to n+1 and all evens up to 2n).

Sub proof 2. "The second sub proof uses the fact proved from the first sub proof." We didn't actually "prove" anything in subproof 1; we just extended our induction hypothesis. We didn't proof anything or do any induction upon it. We just stated something-- namely that we are assuming it is true for all numbers up to odd n and every even up to 2n.

" take any odd number t > 0, by the conjecture, you have to multiply it by 3 and add 1. The result of that, call it r, is an even number always. " Yes, but it's an even number that is larger than 2t so it is useless to us. "So by the result of the first proof, r works with the conjecture since its even. " But it's an even number larger than 2t. "So that means t will work. " Only if t < 2/3 n, which is not outside our range of induction hypothesis.

$\endgroup$
1
$\begingroup$

The key step in your argument says that when $t$ is odd, $r=3t+1$ is even. No other property of $r$ is mentioned. So if the proof were valid, it would remain valid if the "$3$" in $3t+1$ were replaced by any odd number, say $r=101t+1$.

$\endgroup$
0
$\begingroup$

There have already occured some good answers. To deepen the understanding it might be helpful to consider instead of the case 3x+1 the case 181x+1 and do the same logic. Now we have two easily detectable cycles there: would your argument be helpful here as well? Or: where does it break?

$\endgroup$
0
$\begingroup$

I've always felt that induction is not a valid way to prove the Collatz conjecture. Using induction in this context requires assuming that every number less than $n$ reduces to 1. This does not seem like a problem on the surface, but let me provide you with an example.

Suppose $n=11$. I have assumed that $n=2..10$ reduce to 1. But the sequence when $n=11$ starts like this: $11\rightarrow34\rightarrow17\rightarrow...$ Since $17>11$, I first have to prove that 17 reduces to 1 before I can assume that 11 reduces. In other words, assuming [2 to $n$] is true in order to prove $n+1$ is also true does not work for this problem because some of the values in the sequence will exceed $n$. Then the assumption no longer holds, making the proof invalid.

$\endgroup$
  • $\begingroup$ This isn't the only way to do induction - we can argue by induction on orderings other than the usual one. $\endgroup$ – Noah Schweber May 18 '16 at 22:29
  • $\begingroup$ OK, I hadn't thought of that. But what kind of ordering would we use in Collatz? The number of steps away from 1? I can easily build a tree to show numbers close to 1 (who hasn't?), but I don't see how we can use induction on that. $\endgroup$ – scott May 19 '16 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.