26
$\begingroup$

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?

$\endgroup$
18
$\begingroup$

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.)

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

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.