The first we has $ 0\leq x_n\leq 1$ We prove that if $ x_0\in Q$ then $ x_{n}$ is period . Let $ x_0=\frac{p}{q}$ where $ q\in N,0\leq p\leq q-1$ We prove that $ x_n=\frac{p_n}{q}$ by induction. It true for $ n=0$ Suppose it true for $ k$ we prove for $ k+1$ $ x_{k+1}=\frac{q-|q-2p|}{q}=\frac{p_{k+1}}{q}$ where $ p_{k+1}\equiv q-|q-2p|(\mod q)$ So we has prove . Now consider the sequence :$ \{p_k\}$ It take finite value so exist $ k>l\in N$ such that $ p_{k}=p{k-1}$ so $ p_{k+1}=p_{l+1}$ So on we has :$ x_{n}=x_{n+k-l},\forall n\geq l$ So this sequence is period $ k-l$ Now we prove that if the sequence is period then $ x_0\in Q$ Suppose $ x_{n+T}=x_n$ $ x_{n+T},x_n$ is a function linear of $ x_0$ so must $ x_0\in Q$ This problem was be prove.

First of all, the problem statement is wrong - irrational should be replaced with rational, and the sequence can also become periodic only after a finite number of terms. Let $ x_0=0.a_0a_1\cdots _{(base 2)}$. By induction, we have: $ x_n=0.a_{n}a_{n+1}\cdots _{(base 2)}$ or $ x_n=1-0.a_{n}a_{n+1}\cdots _{(base 2)}$. Proof: If $ x_n=0.a_{n}a_{n+1}\cdots _{(base 2)}$, we have 2 cases: case 1: $ a_{n}=0$. So $ x_{n+1}=1-|1-0.a_{n+1}a_{n+2}\cdots |=0.a_{n+1}a_{n+2}\cdots$ case 2: $ a_{n}=1$. So $ x_{n+1}=1-|1-1.a_{n+1}a_{n+2}\cdots |=1-|0.a_{n+1}a_{n+2}\cdots |=1-0.a_{n+1}a_{n+2}\cdots$ If $ x_{n}=1-0.a_{n}a_{n+1}\cdots _{(base 2)}=0.(1-a_{n})(1-a_{n+1})\cdots _{(base 2)}$, we get a similar result: $ x_{n+1}=0.(1-a_{n+1})(1-a_{n+2})\cdots _{(base 2)}$ or $ 1-0.(1-a_{n+1})(1-a_{n+2})\cdots=0.a_{n+1}a_{n+2}\cdots$ Now, $ x_{n}$ becomes periodic if and only if $ x_{n}=x_{m}$ for some $ n>m$. It leads to 2 cases: 1. $ 0.a_{n}a_{n+1}\cdots _{(base 2)}=0.a_{m}a_{m+1}\cdots _{(base 2)} \implies a_{i}=a_{m-n+i}$ for $ i \ge n$, which implies that $ x_0$ is rational (note: we'll use the base 2 representation where there are no infinitely many consecutive 1's) 2. $ 1=0.a_{n}a_{n+1}\cdots _{(base 2)}+0.a_{m}a_{m+1}\cdots _{(base 2)}$. Let $ a=0.a_{n}a_{n+1}\cdots _{(base 2)}, b=0.a_{m}a_{m+1}\cdots _{(base 2)}$. Notice that $ a+b=1, b\cdot 2^{n-m}-a \in Z$ implies that a is rational, and thus $ x_0$ is also rational. It's left to show that $ x_{n}$ is periodic when $ x_{0}$ is rational. Rationality implies that $ a_{n}$ becomes periodic. Let's say that $ a_{n}=a_{n+p}$ for all $ n \ge m$. It's enough to show that some 2 terms of the sequence are equal. Look at $ x_{m}, x_{m+p}, x_{m+2p}$. These 3 terms only have 2 possible values: $ 0.a_{m}a_{m+1}\cdots$ and $ 1-0.a_{m}a_{m+1}\cdots$. So 2 of them are equal (pigeonhole principle), and the period is at most 2p. Q.E.D

Hey, I found a proof which I, myself, think, is pretty and exploits some useful notation, but it's kind of a pain in the butt to write it down like this. So if you think my proof is rather ugly, please say so, so I won't do it again like this. If, on the other hand, you think the proof is quite good and clear, please say so too. Thanks Let [x] = the greatest integer smaller than or equal to x $ f(x) = 1 - |1 - 2x|$ $ f^{0}(x) = x$ $ f^{n}(x) = f(f^{n - 1}(x)) = 1 - |1 - 2f^{n - 1}(x)|$ $ g(x) = min(x - [x], [x] - x + 1)$ Note: $ g(a) = g(b)$ if, and only if, $ a = b (mod 1)$ or $ a = - b (mod 1)$ Theorem. If, and only if, $ f^{0}(x)$ is rational, then, for some distinct a and b: $ f^{a}(x) = f^{b}(x)$ Proof. To proof this we first note that f and the function that measures the distance between a number and the nearest integer of that number, which we defined above as the function g, are quite similar. We will make this somewhat vague statement precise in the following two lemma’s. Lemma 1. $ f^{a}(x) = f^{b}(x)$ for some distinct a and b, is equivalent to the stament: $ g(f^{a"}(x)) = g(f^{b"}(x))$ for some distinct a" and b". Proof of Lemma 1. Since it is trivial that $ f^{a}(x) = f^{b}(x)$ implies that $ g(f^{a}(x)) = g(f^{b}(x))$ we only need to show the converse; if $ g(f^{a"}(x)) = g(f^{b"}(x))$ for some distinct a" and b" then distinct a and b exist for which $ f^{a}(x) = f^{b}(x).$ Since both functions only take values between 0 and 1, we have: $ g(f^{a}(x)) = g(f^{b}(x))$ implies $ f^{a}(x) = f^{b}(x)$ or $ f^{a}(x) = 1 - f^{b}(x)$. In the first case we’re done, so let’s assume $ f^{a}(x) = 1 - f^{b}(x)$ with $ f^{b}(x) > 0,5$. Note that we may assume this without loss of generality, because otherwise we could switch the roles of a and b. But now: $ f^{a + 1}(x) = 1 - |1 - 2f^{a}(x)|$ $ = 1 - (1 - 2f^{a}(x)$ $ = 2f^{a}(x)$ $ = 2(1 - f^{b}(x))$ $ = 1 - (2f^{b}(x) - 1)$ $ = 1 - |1 - 2f^{b}(x)|$ $ = f^{b + 1}(x)$ Which proves Lemma 1. Lemma 2. $ g(f^{n}(x)) = g(x2^{n})$ Proof of Lemma 2. Via induction. For n = 0 the lemma is trivally true. Assume that it holds for some (nonnegative) integer n = k. Then there are 2 cases to consider; Case 1) $ 0,5 \ge f^{k}(x) \ge 0$ Case 2) $ 1 \ge f^{k}(x) > 0,5$ In case 1) we have: $ g(f^{k + 1}(x)) = g(1 - |1 - 2f^{k}(x)|)$ $ = g(1 - (1 - 2f^{k}(x)))$ $ = g(2f^{k}(x))$ $ = g(x2^{k + 1})$ In case 2) we have: $ g(f^{k + 1}(x)) = g(1 - |1 - 2f^{k}(x)|)$ $ = g(1 - (2f^{k}(x) - 1))$ $ = g(2 - 2f^{k}(x))$ $ = g( - 2f^{k}(x))$ $ = g(2f^{k}(x))$ $ = g(x2^{k + 1})$ So in both cases our lemma is also true for n = k + 1, which completes the proof of it. Going back to the proof of our theorem, we first assume that x is irrational and that there exist distinct integral a" and b" for which: $ g(f^{a"}(x)) = g(f^{b"}(x))$, since Lemma 1 told us that that is sufficient to prove the ‘only if’-part. Using Lemma 2 we see that this is equivalent to: $ g(x2^{a"}) = g(x2^{b"}).$ This leads to the equations: $ x2^{a"} = x2^{b"}$ $ (mod 1)$ or $ x2^{a"} = - x2^{b"}$ $ (mod 1)$. Assume the first. (The derivation of the second case goes 'exactly' the same, but I can't find a plus/minus-sign) Then we have, for some integer m: $ x2^{a"} + m = x2^{b"}$ $ m = x2^{b"} - x2^{a"}$ $ m = x*(2^{b"} - 2^{a"})$ $ x = m/(2^{b"} - 2^{a"})$ Which is obviously impossible if x is irrational, since a", b" and m are all integral. All there is left to proof now is the ‘if’ part; rationality implies periodicity. So assume x = p/q (with p and q integral, p nonnegative and q >0). Since the number of powers of 2 that divide q is finite, there must be some i, for which: $ g(f^{i}(p/q)) = g(2^{i}*p/q) = g(p"/q")$ with (q", 2) = 1. So if we can prove our theorem for fractions with denominator coprime to 2, we proved it in general. So assume (q, 2) = 1 and choose n = $ \varphi(q)$ = the number of positive integers that are smaller than and coprime to q. Then, using Euler’s theorem, there must be an integer m, for which: $ mq + 1 = 2^{n};$ $ g(f^{0}(p/q)) = g(p/q)$ $ = g(mp + p/q)$ $ = g((mq + 1)*p/q)$ $ = g(2^{n}*p/q)$ $ = g(f^{n}(p/q))$ And this, together with Lemma 1, implies our theorem. If you read carefully, you may have noticed that we actually proved even more; Let p/q be a given proper fraction. Let $ 2^{i} || q.$ Then, after i or i + 1 (whether p is even or odd) iterations, our function f becomes periodic with a period that divides $ \varphi (q/2^{i})$ EDIT: Note that, in the proof of Lemma 2, I used the fact that g(a) = g(b) implies g(2a) = g(2b), which may not be trivial to everyone, so for completeness' sake, its proof: Assume g(a) = x = g(b). So a = m + y, b = m" + y", with m and m" integral, so that: |y| = |y"| = x. Then we, again, have 2 cases to consider, $ x < 0,25$ (case 1) or $ 0,5 \ge x \ge 0,25$ (case 2); In case 1) we have: $ g(2a) = g(2m + 2y)$ $ = g(2y)$ $ = 2|y|$ $ = 2|y"|$ $ = g(2y")$ $ = g(2m" + 2y")$ $ = g(2b)$ In case 2) we have: $ g(2a) = g(2m + 2y)$ $ = g(2y)$ $ = 1 - 2|y|$ $ = 1 - 2|y"|$ $ = g(2y")$ $ = g(2m + 2y")$ $ = g(2b)$

If $a_0$ irrational then by induction $a_n=r\pm 2^n x$. Thus done. For rationals observe that $\nu_2$ is increasing until it becomes nonnegative. Also if they anyone has odd $q$ in reduced form as denominator then so does its successors. So we’re done by php. (We have in fact proved for eventually periodic)