Csdrhrt

Let $f(x) = 1 - |1 - 2x|$, $a_1 = a$, $a_{n+1} = f(a_n)$. Prove there exists $a in [0, 1]$ such that for every $x in [0, 1]$ there exists a subsequence of $a_n$ convergent to $x$. I've tried to analyze the graph of this function, but couldn't spot anything useful.

First to all we express a generic $xin ]0, 1]$ as a $2$-base decimal sequence
$$
x=0.x_1x_2x_3dotsc x_ndotsc=sum^{+infty}_{i=1}frac{x_i}{2^i}
$$
where $x_iin{0, 1}$. Now remember that $1=0.11111dotsb$ then
$$
1-x=sum^{+infty}_{i=1}frac{1-x_i}{2^i}
$$

Application $f$ as said Hagen von Eitzen does on $x$ this transformation:

• If $x_1=0$ then simply shift to left $x$;


• If $x=1$ then change all $0$ in the "decimal part" with $1$ and vice versa, then shifts it to left.

Let $A={xin ]0, 1[: x $ has a finite representation as decimal in base $2}$ clearly $A$ is dense in $[0, 1]$ so we need to show that for every element of $A$ exists a subsequence of $a_n$ that converges to it. Let $l:mathbb Nrightarrowmathbb N$ (without $0$) such that
$$
2^{l(n)}leq n < 2^{l(n)+1}
$$
(the $2$-length of $n$) and let
$$
j:ninmathbb Nrightarrow{0, 1}
$$
defined in the right manner so that if
$$
a=mathtt{'0.'}+n+j(n)+mathtt{'001'}
$$
then
$$
f^{l(2n+1)}(a)=mathtt{'0.001'}
$$
or in other words the value of next numbers won't be changed after $f$ has passed $2n+j(n)$

Example: if $n=mathtt{'101'}$ and $l(n)=3$ then $j(n)=mathtt{'0'}$ because
$$
mathtt{'0.101,0,001'}\
frightarrowmathtt{'0.0101110'}\
mathtt{'0.101110'}\
frightarrowmathtt{'0.010001'}\
mathtt{'0.10001'}\
frightarrowmathtt{'0.01110'}\
mathtt{'0.1110'}\
frightarrowmathtt{'0.0001'}\
mathtt{'0.001'}\
$$

Observe that
$$
lleft(2n+j(n)right)=l(n)+1
$$

Observe that any element of $A$ is in the form
$$
frac{1}{2^{u-1}}frac{n}{2^{l(n)}}
$$
where $n, uinmathbb N$, we also define $L(n)=sum^{n}_{i=1}[i+l(i)+1]$ and $L(0)=0$

We built $a$ as limit of a sequence $b_n$ created from $b_{n-1}$ in this way:

• We add $n$ zeros at right of $b_{n-1}$;


• Add $n$;


• Add $j(n)$.

In formula
$$
b_0=0\
b_n=b_{n-1}+frac{1}{2^{L(n-1)}}frac{1}{2^n}frac{2n+j(n)}{2^{l(n)+1}}=b_{n-1}+frac{2n+j(n)}{2^{L(n)}}
$$
the term $frac{1}{2^{L(n-1)}}$ is used to left unchanged the preceding elements because $b_{n-1}$ decimal part is $L(n-1)$ long. In this way it's simple to show that
$$
f^{L(n)}(b_n)=0
$$
and
$$
f^{L(n-1)}(b_n)=frac{1}{2^n}frac{2n+j(n)}{2^{l(n)+1}}leqfrac{1}{2^n}frac{n}{2^{l(n)}}+frac{1}{2^{n+l(n)+1}}
$$
(the terms $j(n)$ is used to neutralize the changing effect of $f$) and $b_n$ is a Cauchy sequence so we set $b_nrightarrow a$.

Now if the term $n$ compares in a certain position in $a$ then also $2^kn$ where $kinmathbb N$ appears inside $a$ in a certain point of $a$ representation, because
$$
frac{2^kn}{2^{l(2^kn)}}=frac{n}{2^{l(n)}}
$$

we have

$$
f^{L(2^kn-1)}(a)=frac{1}{2^{2^kn}}frac{2^kn}{2^{l(2^kn)}}+dotsbleqfrac{1}{2^{2^kn}}frac{n}{2^{l(n)}}+frac{1}{2^{2^kn+l(2^kn)+1}}
$$
and for evry $k$ such that $2^kngeq u-1$
$$
f^{L(2^kn-1)+2^kn-u+1}(a)=frac{1}{2^{u-1}}frac{2^kn}{2^{l(2^kn)}}+dotsbleqfrac{1}{2^{u-1}}frac{n}{2^{l(n)}}+frac{1}{2^{u-1+l(2^kn)+1}}\
0leq leftlvert f^{L(2^kn-1)+2^kn-u+1}(a)-frac{1}{2^{u-1}}frac{n}{2^{l(n)}}rightrvertleq frac{1}{2^{u-1+l(2^kn)+1}}rightarrow 0
$$
where $krightarrow +infty$. Then the subsequence is
$$
i_k=L(2^kn-1)+2^kn-u+1rightarrow +infty
$$

Note that $f(x)=2min{x,1-x}$. If the binary expansion of $a$ is
$$a=0.b_1ldots b_n0x_1x_2ldots $$
(where not all $x_i$ are $=1$),
we conclude that the binary expansion of $a_{n+2}$ is $$a_{n+2}=0.x_1x_2ldots$$
So in order to find a subsequence converging to $x$, we only need to make sure that longer and longer prefixes of the binary expansion of $x$ occur after a $0$ in the expansion of $a$ (where we use the expansion $0.1111ldots$ for $x=1$). In order to achieve this for all possible $xin[0,1]$, we just need to make sure that all possible bit patterns occur after a $0$. So let
$$ a=0.0color{red}00color{red}10color{red}{00}0color{red}{01}0color{red}{10}0color{red}{11}0color{red}{000}0color{red}{001}0color{red}{010}0color{red}{011}0color{red}{100}0color{red}{101}0color{red}{110}0color{red}{111}0color{red}{0000}0color{red}{0001}ldots$$

This isn't (now) an answer, but an idea for a simpler solution.

Let $f^n=fcirc fcircdotsbcirc f$ $n$ times and $f^{-n}=f^{-1}circ f^{-1}circdotsbcirc f^{-1}$ $n$ times, the assertion is equivalent to find an $ain ]0, 1[$ such that the set
$$
mathcal{A}={f^n(a):ninmathbb N}
$$
is dense in $]0, 1[$. Suppose that for every $ain ]0, 1[$ exists an interval $I=]x, y[subseteq left]0, frac{1}{2}right[$ (or $left]frac{1}{2}, 1right[$) with length $frac{1}{2^k}$ such that
$$
Icapmathcal{A}=emptyset
$$

Let $L=f^{-1}(I)$ observe that
$$
L=left]frac x2, frac y2right[sqcupleft]1-frac y2, 1-frac x2right[
$$
then $L$ is symmetric and $Lcapmathcal A=emptyset$ because $f^{-1}(mathcal A)supseteqmathcal A$ and
$$
L_1=f^{-1}(L)=frac{L}{2}sqcupleft(1-frac L2right)
$$

In general

For every $Ksubseteq ]0, 1[$ let $K'=f^{-1}(K)$ then
$$
K'=1-K'={1-k:kin K'}
$$
Proof: For every $xin ]0, 1[$ we have $f(x)=f(1-x)$ then
$$
xin K'Leftrightarrow f(x)=f(1-x)in KLeftrightarrow 1-xin K'
$$

and define $L_n$ by recursion. Then we have
$$
L_n=f^{-1}(L_{n-1})=frac{L_{n-1}}{2}sqcupleft(1-frac {L_{n-1}}2right)\
L_n=1-L_n\
lvert L_nrvert = lvert Lrvert =frac{1}{2^k}text{ the Lebesgue measure)}\
L_ncapmathcal A=emptyset
$$

Now we define this new function:
$$
g:xin [0, 1]rightarrowbegin{cases}
2x &text{ if }2xleq 1\
2x -1 &text{ if }2x > 1
end{cases}
$$
Then it holds:

If $K$ satisfy $K=1-K$ then
$$
f^{-1}(K)=g^{-1}(K)
$$
Proof: let $f(x)in K$, if $2xleq 1$ then $f(x)=g(x)$ otherwise $f(x)=2(1-x)$. Because $K$ is symmetric we have
$$
1-f(x)=1-2(1-x)=1-2+2x=2x-1=g(x)in K
$$
and vice versa.

In particular
$$
f^{-1}(L_n)=g^{-1}(L_n)
$$
so we can work with $g$ instead of $f$, observe that $g$ works simply as a "left shift" of $x$ seen in binary representation then if the assertion isn't true for $f$ then it doesn't value neither for $g$, this function is more simpler than $f$ and we can work more simply on it, for example we can use a simplified version of the preceding solution because the "changing effect" doesn't appear when using $g$.