Proof about infinite sum

157 Views Asked by At

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.

1

There are 1 best solutions below

4
On BEST ANSWER

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.