About the proof that every real number in the unit interval is the limit of a sequence of dyadic numbers

Question

Given $x \in (0,1)$, show there exists a sequence $(x_n) \subset \{0,1\}$ such that $x = \sum_{n=1}^\infty \frac{x_n}{2^n}$.

After running into difficult in trying to solve this problem, I found this MSE post, which, to my chagrin, gave me more difficulties. I'm trying to follow John Ma's reasoning. Here's how I understand it:

If $x < \frac{1}{2}$, the choose $x_1 =0$ and therefore $|x-\frac{x_1}{2}| = |x| = x < \frac{1}{2}$, and in fact $x-\frac{x_1}{2} \ge 0$, so in this case we can find $x_1$ for which $0 \le x - \frac{x_1}{2} < \frac{1}{2}$. If, however, $x \ge \frac{1}{2}$, then choose $x_2 =1$, and $|x-\frac{x_1}{2}| < \frac{1}{2}$ holds if and only if $- \frac{1}{2} < x - \frac{1}{2} < \frac{1}{2}$ if and only if $0 < x < 1$. Since $0 < x < 1$ is in fact true, so must $|x-\frac{x_1}{2}| < \frac{1}{2}$. Also, we have $x - \frac{x_1}{2} \ge 0$ since we assumed $x \ge \frac{1}{2}$. Hence, in either case we found $x_1 \in \{0,1\}$ for which $0 \le x-\frac{x_1}{2} < \frac{1}{2}$ holds. Now assume that $x_1,...x_n \in \{0,1\}$ have been chosen such that $0 \le x - \sum_{k=1}^n \frac{x_k}{2^k} < \frac{1}{2^n}$. From this we want to show that it is possible to choose $x_{n+1} \in \{0,1\}$. If $x - \sum_{k=1}^n \frac{x_k}{2^k} < \frac{1}{2^{n+1}}$, then choose $x_{n+1} = 0$ and we obtain $x - \sum_{k=1}^{n+1} \frac{x_k}{2^k} < \frac{1}{2^{n+1}}$. If, however, $x - \sum_{k=1}^n \frac{x_k}{2^k} \ge \frac{1}{2^{n+1}}$, choose $x_{n+1} = 1$. Then $x - \sum_{k=1}^{n+1} \frac{x_k}{2^k} = (x - \sum_{k=1}^n \frac{x_k}{2^k}) - \frac{1}{2^{n+1}}$

But here's the problem: why is $x - \sum_{k=1}^{n+1} \frac{x_k}{2^k}$ nonnegative? If that can't be shown, then I cannot appeal to Squeeze lemma to show $x = \sum_{n=1}^\infty \frac{x_n}{2^n}$. I could really use some help. Thanks in advanced!

Answer 1

The following argument offers an alternative proof; the contrast between different proofs can be instructive.

For any $k$, define

$\tag 1 R_k = \{\sum_{n=1}^k \frac{x_n}{2^n} \; | \; x_n \in \{0,1\} \land \sum_{n=1}^k \frac{x_n}{2^n} \le x\}$.

This is a finite set with at most $2^k$ elements.

Proposition 1: For every $k$,

$\tag 2 x - \text{max}(R_k) \le 2^{-k} $

Proof
To get a contradiction, assume that $x_n$ defines the maximum number in $R_k$ and

$\tag 3 x - \sum_{n=1}^k \frac{x_n}{2^n} \gt 2^{-k} $

It can't be true that $x_n = 1$ for all $n$, since then $x \gt 1$. But then since

$\tag 4 \sum_{n=1}^k \frac{x_n}{2^n} + 2^{-k} \le x $

the $2^{-k}$ number can be 'absorbed' into the sigma expression form, so that a another number can be found in $R_k$ greater than the number defined with the $x_n$. $\quad \blacksquare$

It is now easy, using $\text{(2)}$, to show that the increasing sequence $\text{max}(R_k)$ converges to $x$.

---

Note: Although induction wasn't explicitly used, the $\sum$ notation (an 'induction machine') is carrying the proof construction.

Answer 2

(1).Let $x_1=0$ if $0<x<1/2$ and $x_1=1$ if $1/2\leq x<1.$ Let $y_1=x_1/2.$ We define the sequences $(x_n)_{n\in \Bbb N}$ and $(y_n)_{n\in \Bbb N}$ as follows:

(2). Suppose $y_n\leq x.$ Let $x_{n+1}=0$ if $x<y_n+2^{-(n+1)}.$ Let $x_{n+1}=1$ if $x\ge y_n+2^{-(n+1)}.$ And let $y_{n+1}=y_n+x_n2^{-(n+1)}.$ In both cases we have $y_n\leq x\implies y_{n+1}\leq x.$

And we have $y_1\leq x.$ So by induction we have $y_n\leq x$ for all $n$.

(3). We have $y_n\geq x- 2^{-n}\implies y_{n+1}\geq x-2^{-(n+1)}.$ Proof: Suppose $y_n\geq x-2^{-n}.$ Then

$\quad$(i).If $y_n\leq x-2^{-(n+1)}$ then $x_{n+1}=1$ so $\quad y_{n+1}=y_n+2^{-(n+1}\geq (x-2^{-n})+2^{-(n+1)}=x-2^{-(n+1)}.$

$\quad$(ii). If $y_n>x-2^{-(n+1)}$ then $x_{n+1}=0$ so $y_{n+1}=y_n>x-2^{-(n+1)}.$

In both (i) and (ii) we have $y_{n+1}\geq x-2^{-(n+1)}.$

And we have $y_1\geq x-2^{-1}.$ So $y_n\geq x-2^{-n}$ for all $n$ by induction.

(4). Since $x-2^{-n}\leq y_n\leq x$ for all $n,$ we have $x=\lim_{n\to \infty}y_n=\sum_{n=1}^{\infty}x_n2^{-n}.$

Remark. In (2) we use recursion and induction together, to define $x_{n+1}$ and $y_{n+1}$ recursively from $y_n$, with the inductive hypothesis that $y_n\leq x.$ If you wanted, you could instead say " If $y_n>x$ then let $x_{n+1}=1=y_{n+1}$ " ( or some other arbitrary values) for a purely recursive def'n, and then prove separately that $y_n\leq x$ for all $n$ by induction.

Answer 3

All that is necessary is to highlight/expand on what the OP has already written out.

Let $P(n)$ be the inductive hypothesis and we write as true

$\tag 1 P(n): \quad 0 \le x - \sum_{k=1}^n \frac{x_k}{2^k} < \frac{1}{2^n}, \; \text{ with } x_1,...x_n \in \{0,1\}$

We need to set $x_{n+1} = 0$ or $x_{n+1} = 1$ such that $P(n+1)$ is true, i.e.

$\tag 2 0 \le x - \sum_{k=1}^{n+1} \frac{x_k}{2^k} < \frac{1}{2^{n+1}}$

Case 1: $x - \sum_{k=1}^n \frac{x_k}{2^k} < \frac{1}{2^{n+1}}$
In this case $\text{(2)}$ will be true by simply setting $x_{n+1} = 0$.

Case 2: $x - \sum_{k=1}^n \frac{x_k}{2^k} \ge \frac{1}{2^{n+1}}$
Using $\text{(1)}$ we can write

$\tag 3 \frac{1}{2^{n+1}} \le x - \sum_{k=1}^n \frac{x_k}{2^k} < \frac{1}{2^n}$

Subtracting $\frac{1}{2^{n+1}}$ we can write

$\tag 4 \frac{1}{2^{n+1}} - \frac{1}{2^{n+1}} \le [x - \sum_{k=1}^n \frac{x_k}{2^k}] -\frac{1}{2^{n+1}} < \frac{1}{2^n} - \frac{1}{2^{n+1}}$

or

$\tag 5 0 \le [x - \sum_{k=1}^n \frac{x_k}{2^k}] -\frac{1}{2^{n+1}} < \frac{1}{2^{n+1}}$

So if we set $x_{n+1} = 1$ statement $\text{(2)}$ will be true.