1
$\begingroup$

Let's say we've a function similar to the function in Collatz conjecture. $$ f(n)= \begin{cases} 1 \ \ \ \ \ \ \ \ \ \text{if $n=1$}\\ \tfrac12n \ \ \ \ \ \ \text{if $n \equiv 0 \ \ $ (mod 2)}\\ n-1 \ \ \ \text{if $n \equiv 1 \ $ (mod 2) }\\ \end{cases} \\ , \forall \ \ n \in \mathbb{Z}^+ $$

Now, Can we prove that this will go to $1$ , or maybe more formally:

$$ f^m(n) = 1, m \to \infty $$

If yes, what steps would we take?

$\endgroup$
  • $\begingroup$ What do you mean "converge to $n$"? $\endgroup$ – vrugtehagel May 5 '17 at 7:45
  • $\begingroup$ Sorry, meant 'one' $\endgroup$ – cipher May 5 '17 at 7:46
  • $\begingroup$ You must restrict the domain of $n$, because "otherwise" can also include zero and negative numbers. Note also, that your problem-statement "hopes" that the reader assumes $n$ as integer (which might be "obviously" implied because of the term "even" - but this is still sloppy). So to make a formal proof you need to insert that restrictions in your problem-statement. $\endgroup$ – Gottfried Helms May 5 '17 at 10:25
  • 1
    $\begingroup$ Yes, I think it is fine now! $\endgroup$ – Gottfried Helms May 6 '17 at 19:35
  • 1
    $\begingroup$ @cipher: coming home just now, being tired. Perhaps tomorrow evening... $\endgroup$ – Gottfried Helms May 6 '17 at 19:51
4
$\begingroup$

This will always go to $1$.

Assume $n$ is even; then $f(n)=\tfrac12n<n$. Assume $n>1$ is odd; then $f(n)=n-1<n$. Thus, $f(n)<n$ for all $n>1$. This makes sure that we decrease every time we apply $f$, thus, we must reach $1$ or less at some point, and since $f(n)\ge 1$, we know this must be $1$.

$\endgroup$
  • $\begingroup$ Thanks, I understood the proof. But does this count as a formal proof? I'd love to see how a formal proof for this is written. $\endgroup$ – cipher May 5 '17 at 8:06
  • 1
    $\begingroup$ This certainly counts as formal proof. $\endgroup$ – vrugtehagel May 5 '17 at 8:08
  • $\begingroup$ I think one should mentioned that f(n)>=1, because your arguments also are valid for a function f(n)=n-2(n!=1) f(n)=1 (n=1). $\endgroup$ – miracle173 May 5 '17 at 8:20
  • $\begingroup$ Right. I edited the post to clarify that part. $\endgroup$ – vrugtehagel May 5 '17 at 8:43
  • $\begingroup$ @vrugtehagel formally, I guess you need to point out that subtracting by $1$ is somehow potent enough to get us to $1$ in the sense that there are only countably many whole numbers and $x\to x-1$ is not convergent on some limit point greater than $1$. That $1$ is the least positive integer is also required. These are trivial for your example, but perhaps material as examples of formality in relation to the real Collatz. $\endgroup$ – samerivertwice May 8 '17 at 15:22

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.