# Convergence of $u_{n+1}= 2\left| u_n \right| -1$

Find all $u_0$ such that the recursive sequence defined by $u_{n+1}= 2\left| u_n \right| -1$ converges.

Let $f(x) = 2\left|x\right|-1$. If $(u_n)$ converges, it converges to a fixed point of $f$, that is to say $-\frac 13$ or $1$.

Furthermore, if $(u_n)$ converges to $l\in\{-\frac 13, 1\}$ , the mean value theorem yields, for some large enough $n_0$, $$\forall n\geq n_0, \displaystyle \left|\frac{u_{n+1}-l}{u_{n}-l} \right|=2$$

Since $\lim_{n\to \infty}(u_{n}-l)= 0$ it must be that $u_{n_1}=l\;\;$ for some $n_1\geq n_0$ which implies $u_n=l$ for all $n\geq n_1$.

Note that $u_0<-1$ or $u_0>1$ both lead to divergence of $(u_n)$

Therefore, finding the $u_0$ for which the sequence converges amounts to studying the following set $$X:= \{x\in[-1,1], \exists p\in \mathbb N, f^{(p)}(x)\in\{-\frac 13, 1\}\}$$

Is it possible to determine what this set contains exactly ? Certainly $X\cap (\mathbb R \setminus \mathbb Q)=\emptyset$.

• Hint: Study the effect of $x\mapsto|2x-1]$ on numbers in $[0,1]$, using their dyadic expansion $x=0.x_1x_2\ldots$ Deduce that $X$ collects the dyadic numbers (those whose expansion terminates).
– Did
Sep 11, 2016 at 13:34
• @Did what do you mean with $x\mapsto|2x-1]$, I've never seen this notation before Sep 11, 2016 at 13:39
• $u_0$ has to be rational. E.g. $x:=\frac{1}{2}$: $\,\,\frac{1}{2}\to0\to-1\to1\,$; $\,x:=\frac{2}{3}$: $\,\,\frac{2}{3}\to\frac{1}{3}\to-\frac{1}{3}$. I think, the convergence to $\{-\frac{1}{3};1\}$ is only possible with rational numbers $\frac{a}{3^m\cdot 2^n}$ where $m\in\{0;1\}$, $n\in\mathbb{N}_0$ and $a\in\mathbb{Z}\setminus\{0\}$. Sep 11, 2016 at 16:15
• The function $g$ defined by $g(x)=|2x-1|$.
– Did
Sep 11, 2016 at 18:11
• @Did it's indeed very insightful, thanks for the suggestion Sep 12, 2016 at 20:21

Note that if $x\in I=[-1,1]$, then $f(x)\in I$, and as you have remarked, for $x$ to be in $X$, we need that $x\in I\cap \mathbb{Q}$.
Let $u_0=p/q$ in $X$, with $p$ prime to $q\geq 1$. Suppose that there exists a prime $l$, $l\not = 2,3$, such that $l$ divide $q$. Then if we set $u_1=\frac{p_1}{q_1}=\frac{2|p|-q}{q}$ ($p_1$ prime to $q_1$), we see that we have also that $l$ divide $q_1$. Hence as we want by a finite number of iteration to arrive at $1$ or $-1/3$, the only prime divisors of $q$ are possibly $2$ and $3$. The same argument works if $9$ divide $q$: we see that $9$ divide $q_1$. It remain to show that if $q=2^l$ or $q=3 2^l$, then $p/q$ is in $X$, If I am not wrong, it is easy.
• @LeGrandDODOM: It is $|p|$ in fact..;a misprint, sorry Sep 11, 2016 at 15:39