The distances in fractions and finite fractional binary representations

36 Views Asked by At

We have to prove through induction on $n$ that for all positive integers $n$, and for any $x \in [0, 1)$, there is some $x_0 \in [0, 1)$ so that $x_0$ can be written in a finite fractional binary representation ($FB$) and $0 \leq x - x_0 \leq \frac{1}{2^n}$.

I tried to put this into words and this is how I understand it: You can always pick a number that is $FB$ and its distance with $x$ is small. I'm having trouble on how I can pick any close number and how any number I pick is $FB$.

I think if I'm given a number like $(0.00110011)_2$, I can remove the last $1$ to make it smaller.

I don't know where to start though but I think this idea is helpful.

1

There are 1 best solutions below

2
On

Let $x\in[0,1)$ and $n\in\Bbb N$ be given. Then the set $A:=\{\,k\in\Bbb N\mid 2^nx> k\,\}$ is non-empty (it contains $2^n$, for example). Hence $A$ has a minimal element $k_0$ (this follows by the well-ordering principle - or by induction if you prefer). Clearly, $k_0>0$, hence $k_0-1\in\Bbb N$. As $k_0-1\notin A$, we conclude $k_0-1\le 2^nx<k_0$. Now let $x_0=\frac {k_0-1}{2^n}$ and show that it has the desired property.