# Writing real numbers as sums of zeros and ones

Call a number $\delta\in(0,1)$ "good" if it satisfies the following property:

Every real number $a\in(0,1)$ can be written as an infinite sum of the form: $$a = \sum_{i=1}^\infty \delta^i a_i$$ where $a_i\in\{0,1\}$.

What numbers are good?

I know that $1/2$ is good, since when $\delta=1/2$, the $a_i$ are just the digits in binary representation of $a$.

On the other hand, $1/3$ is not good, since in order to represent a real number in ternary, we also need the digit 2.

It is easy to prove that every $\delta<1/2$ is not good, since the maximum number that can possibly be represented is $\frac{\delta}{1-\delta}$, and it is strictly smaller than 1.

My conjecture is that every $\delta\in [1/2,1)$ is good. Is this true?

Yes. Recall that the infinite sum is shorthand for

$$a = \lim_{n \to \infty} \sum_{i=1}^n \delta^i a_i$$

That is, $a$ is the limit of a sequence of partial sums of that series. Thus, to show that the partial sums have $a$ as their limit, we must show that we can get arbitrarily close to $a$ with those partial sums.

You can establish this as follows (this is just a sketch, you need to make this more formal): Imagine that all the $a_i$ are $1$ initially. That will make the infinite sum $\delta/(1-\delta)$, which is greater than or equal to $1$ (and therefore greater than the target) whenever $\delta \in [1/2, 1)$. Now employ a greedy algorithm: At each stage, remove the largest $\delta^i$ that you can without lowering the sum below $a$. Since the sequence of $\delta^i$ have $0$ as a cluster point, and removing any $\delta^i$ always leaves a "residue" smaller than $\delta^i$ (because $1/2 \leq \delta < 1$), we can get as close as we like to $a$.

Therefore, we can write any value $a \in (0, 1)$ this way. (In fact, we can write $0$ and $1$ this way, too.)

• Let me just comment that finding such $\delta^i$ to remove is possible due to well-ordering of $\mathbb N$. – Ennar Nov 11 '15 at 19:13
• Nice! ${}{}{}{}$ – MarsOneRover Nov 11 '15 at 19:15
• Thanks! I wrote an answer that tries to formalize the intuition in your answer. Is that what you meant? – Erel Segal-Halevi Nov 12 '15 at 8:29
• Looks right to me at first glance. – Brian Tung Nov 13 '15 at 2:40

Following the hint in Brian Tung's answer, I am trying to write a formal proof.

Let $\delta\in[1/2,1)$ and $D=\frac{\delta}{1-\delta}\geq 1$.

Claim: Given a number $a\in[0, D)$, for every integer $N\geq 0$ there exists a sequence of numbers $a_1,\dots, a_N$, all in $\{0,1\}$, such that:

$$D\cdot \delta^N > a-\sum_{i=1}^N{\delta^i\cdot a_i} \geq 0$$

Proof: By induction on $N$. For $N=0$, the sequence is empty and we get:

$$D > a \geq 0$$ which is given. Suppose the claim is true for $N$. Mark:

$$b_N = a - \sum_{i=1}^N{\delta^i\cdot a_i}$$ so by assumption:

$$D\cdot \delta^N > b_N \geq 0$$

Define $a_{N+1}$ in the following way:

• If $D\cdot \delta^{N+1} > b_N$, then set $a_{N+1}=0$. Then $b_{N+1} = b_N$ and it satisfies the requirement: $D\cdot \delta^{N+1} > b_{N+1} \geq 0$.
• Otherwise, set $a_{N+1}=1$. Then $b_{N+1} = b_N - \delta^{N+1}$ and:
• $b_{N+1} \geq D\cdot \delta^{N+1} - \delta^{N+1} = (D-1)\delta^{N+1} \geq 0$, since $D\geq 1$.
• $b_{N+1} < D\cdot \delta^N - \delta^{N+1} = D\cdot\delta^N(1-\delta) = \delta^{N+1} \leq D\delta^{N+1}$, again since $D\geq 1$. Hence: $b_{N+1} < D\cdot \delta^{N+1}$ as required. $\square$

Corollary:

$$a = \sum_{i=1}^\infty{\delta^i\cdot a_i}$$