1
$\begingroup$

I've a function that looks like the one mentioned in Collatz Conjecture $$ f(n)= \begin{cases} 1 & \text{if $n=1$}\\ \tfrac12n & \text{if $n \equiv 0 \ \ $ (mod 2)}\\ 3n+1 & \text{if $n \equiv 1 \ $ (mod 2) }\\ \end{cases} \\ , \forall \ \ n \in \mathbb{Z}^+ $$

I want to prove that

$$ f^m(n) \not= f^{m-1}(n), \forall{m} \in \mathbb{Z}^+ - \{1\}, n>1 $$

I decided to go with induction method,

Base Step $m = 2$

$$ let \ \ f(n) = o \\ f^2(n) = f(f(n)) = f(o) \\ if \ \ o \ \text{ is even}, \ \ f(o) = o/2, \ \ o \not = o/2 \\ if \ \ o \ \text{ is odd}, \ \ f(o) = 3o +1, \ \ o \not = 3o + 1 \\ $$ Note: The non-equals expressions are true for the set of positive integers, the assumption is that the function above has both its domain and range in positive integers

Induction Step Assumption P(m) holds, to Prove P(m+1) holds

$$ \text{ To Prove } \ \ f^{m+1}(n) \not = f^m(n) \\ \text{ } \\ \text{ }\\ \text{Assume } f^m(n) = O \\ f^{m+1} = f(f^{m}(n)) = f(O), \\ f(O) = O/2 , \text{if O is even, and} O \not = O/2 \\ f(O) = 3O + 1 , \text{if O is odd, and} O \not = 3O + 1 \\ \text{which proves that $O \not = f(O) \implies f^m(n) \not = f^{m+1} (n)$ } $$

By the method of induction, we can now say that $$ f^m(n) \not= f^{m-1}(n), \forall{m} \in \mathbb{Z}^+ - \{1\} $$


Now I've some questions:

  1. Is the above proof correct? If incorrect, which assumption(s) were wrong?
  2. If the proof is correct, won't it mean that all the numbers created by the above function $f(n)$ in its every successive iteration is unique?
  3. If the statement 2 is correct, doesn't it imply that if I remove the first condition $(n = 1)$ , the function $f(n)$ will always be on a $4 \to 2 \to 1$ cycle, which in turn could prove Collatz conjecture?
$\endgroup$
  • $\begingroup$ @DavidK True. Thanks for pointing out. I'll edit it to restrict n = 1 . $\endgroup$ – cipher May 6 '17 at 19:59
  • $\begingroup$ Let $m=2,n=2$; then $f^m(n)=f(f(2))=f(1)=1=f(2)=f^{m-1}(2),$ so the "theorem" is still false. $\endgroup$ – David K May 6 '17 at 20:00
  • $\begingroup$ Also false for $m\geq3,n=4,$ and for $m\geq4,n=8,$ for $m\geq6,n=5,$ etc. $\endgroup$ – David K May 6 '17 at 20:02
  • $\begingroup$ Here's a function for which your statement is true: $f(n)=2n.$ Yet obviously this function does not always lead to a $4\mapsto2\mapsto1\mapsto4$ cycle. $\endgroup$ – David K May 6 '17 at 20:04
  • $\begingroup$ @DavidK Wow, thanks for pointing these. It would be great if you could write these as an answer. $\endgroup$ – cipher May 6 '17 at 20:06
2
$\begingroup$
  1. Induction is not necessary. You prove the whole statement in the induction step alone (without use of the induction hypothesis).

  2. I'm not sure what you mean by this. You'll have to be more precise. All you know is $f^m(n) \neq f^{m+1}(n)$, but it's entirely possible that $f^m(n)=f^{m+2}(n)$, etc.

  3. How do you know there's not some other cycle other than $1 \mapsto 4 \mapsto 2 \mapsto 1$?

  4. I would highly urge you to never use $o$ or $O$ as variables/constants.

$\endgroup$

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.