# Correctness in Proof By Induction for a Collatz-ish function

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?
• @DavidK True. Thanks for pointing out. I'll edit it to restrict n = 1 . May 6, 2017 at 19:59
• 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. May 6, 2017 at 20:00
• Also false for $m\geq3,n=4,$ and for $m\geq4,n=8,$ for $m\geq6,n=5,$ etc. May 6, 2017 at 20:02
• 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. May 6, 2017 at 20:04
• @DavidK Wow, thanks for pointing these. It would be great if you could write these as an answer. May 6, 2017 at 20:06

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.