How to prove that this function will converge to $1$?

Question

I have an assignment for tomorrow that ask me to prove that the sequence/function

$f(x) =\begin{cases}\dfrac x2\quad\quad\quad\text{if } x\text{ is even}\\3x+1\quad\;\text{if }x\text{ is odd}\end{cases}$

(where $x$ is a natural number)

will converge to $1$.

I have tried by hand and it seems to work but I have no idea where to start.

Thanks a lot.

What do you mean by it converges to 1? $f$ is just a function. What if $f$ is not an integer? — copper.hat, Nov 06 '14 at 07:06
The edit seems to say it's a sequence, $f : \Bbb N \to \Bbb N$ I guess. But then it doesn't seem to converge to $1$ at all. — Platehead, Nov 06 '14 at 07:09
@Platehead do you have a counter example? it seems to work with everything I tried? — Jerry Taylor, Nov 06 '14 at 07:09
I have no idea what you could possibly mean by converges to 1 in this case. — copper.hat, Nov 06 '14 at 07:10
@copper.hat for example for x=5, f(5)=16, f(16)=8, f(8)=4, f(4)=2, f(2)=1 — Jerry Taylor, Nov 06 '14 at 07:11
You have rediscovered the Collatz conjecture: http://en.wikipedia.org/wiki/Collatz_conjecture. — Martín-Blas Pérez Pinilla, Nov 06 '14 at 07:11
@Martín-BlasPérezPinilla I just want to sleep, do you have a solution to this? My assignment is due for tomorrow. Please — Jerry Taylor, Nov 06 '14 at 07:12
If is your assignment, you've been joked. No solution is known. — Martín-Blas Pérez Pinilla, Nov 06 '14 at 07:13
@Martín-BlasPérezPinilla what the hell? are you sure? Why would my prof do something like that? Are you sure? — Jerry Taylor, Nov 06 '14 at 07:14
@JerryTaylor: Tell your prof. that you stayed up all night and skipped other classes trying to prove it and you were not able to. See how she reacts. — copper.hat, Nov 06 '14 at 07:16
@JerryTaylor Better yet, tell your prof. that you stayed up all night, and you found the assignment slightly harder than previous assignments, but you finally finished it. Then plunk down a notebook containing 100 pages of cramped, totally illegible handwriting, with an excited "= 1 QED!" at the end. — Chris Culter, Nov 06 '14 at 07:21
@Aditya Good point, sort through your trash and scrawl on the backs of junk mail envelopes and coffee-stained napkins instead. It'll be even more authentic! — Chris Culter, Nov 06 '14 at 07:28

Christian Blatter · Answer 1 · 2020-12-18T14:59:55.133

1

You are given a starting value $x_0\in{\mathbb N}$ and consider the integer sequence $(x_n)_{n\geq0}$ recursively defined by $$x_{n+1}:=f(x_n)\qquad(n\geq0)\ .$$ It is impossible that this sequence converges to $1$, because this would enforce $x_n=1$ for all large $n$, whereas $f(1)=4$.

edited Dec 18 '20 at 14:59

answered Nov 06 '14 at 12:49

Christian Blatter

226,825

How to prove that this function will converge to $1$?

1 Answers1