Proof about infinite sum Define recursively-defined function $f_x:N\to\{{0,1\}}^N$ where x belongs to [0,1): 
For $n=1$,$f_x(1)=0$ if $x$ belongs to $[0,1/2)$, $a_1=0$, $b_1=1/2$ in this case; 
$f_x(1)=1$ if $x$ belongs to $[1/2,1)$, $a_1=1/2$, $b_1=1$ in this case. 
For $n\ge2$, $f_x(n)=0$ if $x$ belongs to $[a_{n-1},(a_{n-1}+b_{n-1})/2)$, in this case, $a_n=a_{n-1}$, $b_n=(a_{n-1}+b_{n-1})/2$; 
$f_x(n)=1$ if $x$ belongs to $[(a_{n-1}+b_{n-1})/2,b_{n-1})$, in this case $a_n=(a_{n-1}+b_{n-1})/2$, $b_n=b_{n-1}$. 
How to prove $\sum_{n=0}^{\infty}f_x(n)/2^n=x$? 
I think to let epsilon equals to $1/2^n$ is a possible way but I don't know what to do after this.
 A: What $f_x$ computes is the binary expansion of $x$, ie
$$
\sum_{n\geq 0}\frac{f_x(n)}{2^n}=x.
$$
The sequences $a_n,b_n$ are constructed in such a way that
$$
x\in [a_n,b_n)
$$
for all $n$. 
These are dyadic numbers. And we go down the binary tree of dyadic numbers as $n$ grows.
We can easily prove by induction that 
$$
b_n-a_n=\frac{1}{2^n}.
$$
At step $n$, we have
$$
\sum_{k=0}^n\frac{f_x(k)}{2^k}=a_n\leq x <b_n.
$$
The inequalities follow from the construction and have already been observed.
Now for the lhs equality, we will use induction.
This indeed true for $n=1$.
Now assume it is true for $n-1$.
Case 1: $f_x(n)=0$ then $a_n=a_{n-1}$ and you add zero to the partial sum so it remains equal to $a_n$.
Case 2: $f_x(n)=1$ then
$$
a_n=\frac{a_{n-1}+b_{n-1}}{2}=\frac{a_{n-1}+a_{n-1}+1/2^{n-1}}{2}=a_{n-1}+\frac{1}{2^n}.
$$
And $1/2^n$ is exactly what you add to the partial sum in this case. So it remains equal to $a_n$.
This completes the induction.
So $a_n$ is nondecreasing bounded above by $x$, $b_n$ is nonincreasing bounded below by $x$, and $b_n-a_n$ tends to $0$. Therefore
$$
\lim_{n\rightarrow +\infty} a_n=\lim_{n\rightarrow+\infty} b_n=x.
$$
The result follows.
