Dyadic Expansion-Proof? Working through a measure theory textbook, and would like to understand dyadic expansions before I can understand its connections with the law of large numbers. I want to see this proved in detail,
For a mapping $F$ from $\Omega=(0,1]$ into itself given by $$F\omega=\begin{Bmatrix}
2\omega & \mbox{if } 0< \omega\leqslant\frac{1}{2} \\ 
2\omega-1 & \mbox{if } \frac{1}{2}< \omega\leqslant1 
\end{Bmatrix} $$ and $$d_1(\omega)=\begin{Bmatrix}
0 & \mbox{if } 0< \omega\leqslant\frac{1}{2} \\ 
1 & \mbox{if } \frac{1}{2}< \omega\leqslant1 
\end{Bmatrix} $$ and $d_i(\omega)=d_1(F^{i-1}\omega)$ , How do we prove that $\omega=\sum_{i=1}^{\infty }d_i(\omega)/{2^i}$?
 A: The Idea: Suppose that $0.b_1b_2b_3\dots$ is the binary expansion of $\omega$, non-terminating if there is a choice. The map $F$ is essentially just a shift map: it takes $0.b_1b_2b_3\dots$ to $0.b_2b_3b_4\dots$. The map $d_1$ then picks off the first bit of the expansion, and in general $d_n$ picks off the $n$-th bit. Here are the details.
It’s not hard to check that
$$F^2(\omega)=\begin{cases}
4\omega,&\text{if }0<\omega\le\frac14\\\\
4\omega-1,&\text{if }\frac14<\omega\le\frac12\\\\
4\omega-2,&\text{if }\frac12<\omega\le\frac34\\\\
4\omega-3,&\text{if }\frac34<\omega\le1\;.
\end{cases}$$
In fact, it’s not hard to prove by induction on $n$ that for $k=0,\dots,2^n-1$, $F^n(\omega)=2^n\omega-k$ iff $\frac{k}{2^n}<\omega\le\frac{k+1}{2^n}$. And $\frac{k}{2^n}<\omega\le\frac{k+1}{2^n}$ iff $k<2^n\omega\le k+1$ iff $k=\lceil 2^n\omega\rceil-1$, so if we wish, we can simply write $F^n(\omega)=2^n\omega-\lceil 2^n\omega\rceil+1$.
Next, observe that $$0<\omega-\frac{d_1(\omega)}2\le\frac12$$ for all $\omega\in(0,1]$. Suppose that $$0<\omega-\sum_{k=1}^n\frac{d_k(\omega)}{2^k}\le\frac1{2^n}\;.\tag{1}$$
Then $$0<2^n\omega-\sum_{k=1}^nd_k(\omega)2^{n-k}\le 1\;.$$ Let $m=\sum_{k=1}^nd_k(\omega)2^{n-k}$; $m$ is an integer, and $m<2^n\omega\le m+1$, so $m+1=\lceil 2^n\omega\rceil$, and $2^n\omega-\lceil 2^n\omega\rceil+1=2^n\omega-m$.
Now $d_{n+1}(\omega)=d_1(F^n(\omega))=d_1(2^n\omega-\lceil 2^n\omega\rceil+1)=d_1(2^n\omega-m)$; this is $1$ if $2^n\omega-m>\frac12$ and $0$ otherwise. But 
$$\begin{align*}
2^n\omega-1>\frac12&\text{ iff }\omega-\frac{m}{2^n}>\frac1{2^{n+1}}\\
&\text{ iff }\omega-\sum_{k=1}^n\frac{d_k(\omega)}{2^k}>\frac1{2^n}\\
&\text{ iff }\omega-\sum_{k=1}^{n+1}\frac{d_k(\omega)}{2^k}>0\;,
\end{align*}$$ 
so in all cases $$0<\omega-\sum_{k=1}^{n+1}\frac{d_k(\omega)}{2^k}\le\frac1{2^{n+1}}\;.\tag{2}$$
(The second inequality in $(2)$ follows from the fact that Since $2^n\omega-m\le 1$.) Thus, $(1)$ implies $(2)$, and by induction $(1)$ holds for all $n\ge 1$. Since $\frac1{2^n}\to 0$ as $n\to\infty$, it follows that $$\omega=\sum_{k=1}^\infty\frac{d_k(\omega)}{2^k}\;.$$
