TAOCP 4.1 Exercise 22

Section 4.1: Positional Number Systems

Exercise 22. [HM25] Let $\alpha = -\sum_{m>1} 10^{-m!}$. Given $\epsilon > 0$ and any real number $x$, prove that there is a "decimal" representation such that $0 < |x - \sum_{k \ge 0} a_k 10^k| < \epsilon$, where each $a_k$ is allowed to be only one of the three values $0$, $1$, or $\alpha$. (No negative powers of 10 are used in this representation!)

Verified: no
Solve time: 3m13s

---

Solution

Let $x$ be an arbitrary real number and $\epsilon > 0$ be given. We aim to construct a "decimal" representation

$X = \sum_{k \ge 0} a_k 10^k, \qquad a_k \in {0,1,\alpha},$

such that

$0 < |x - X| < \epsilon.$

We proceed by a greedy construction, analogous to standard decimal expansions but adapted to the restricted digit set ${0,1,\alpha}$.

Let us define the sequence of partial sums $(S_n)$ by

$S_0 = 0, \qquad S_{n+1} = S_n + a_n 10^n,$

where $a_n$ is chosen at each stage to minimize $|x - S_{n+1}|$ while respecting the restriction $a_n \in {0,1,\alpha}$. We show that this procedure eventually produces a sum $S_N$ satisfying $0 < |x - S_N| < \epsilon$.

Step 1: Choice of digits.

At the $n$-th stage, suppose that $S_n$ has been constructed. Define the residual

$r_n = x - S_n.$

We select $a_n$ as follows:

1. If $|r_n| < \epsilon$, stop.
2. Otherwise, choose $a_n \in {0,1,\alpha}$ such that $|r_n - a_n 10^n|$ is minimized.

We need to verify that such a choice is always possible.

Step 2: Estimating the remaining error.

By the definition of $\alpha$,

$|\alpha| = \sum_{m>1} 10^{-m!} < \sum_{k=2}^\infty 10^{-k} = \frac{1}{90}.$

Hence, $\alpha \cdot 10^n < 10^{n}/90$ for all $n \ge 0$. The sequence $10^{-m!}$ decays extremely rapidly, so the "carry-over" effects in the greedy procedure are negligible compared to $10^n$. Consequently, at each step, the residual error can be reduced below any preassigned $\epsilon$ by selecting $n$ sufficiently large.

Formally, for any $\epsilon > 0$, choose $N$ such that $10^N > 1/\epsilon$. Then for $n \ge N$, we can select $a_n = 0$, guaranteeing that the contribution of higher terms

$\sum_{k > n} a_k 10^k \le \sum_{m>1} \alpha 10^{n} 10^{-m!} < \epsilon.$

Step 3: Convergence of the construction.

At each stage, the greedy choice ensures that the partial sum $S_n$ approximates $x$ ever more closely. Since the residual terms beyond stage $n$ are bounded by

$\sum_{k>n} 10^k \cdot \max{1,\alpha} \cdot 10^{-k!} \le \sum_{m > (n+1)!} 10^{-m} < \epsilon$

for sufficiently large $n$, the series converges. The construction guarantees that $0 < |x - S_n| < \epsilon$ for some $n$.

Step 4: Positivity of the error.

To ensure $|x - X| \neq 0$, observe that $\alpha$ is strictly negative. Therefore, by choosing $a_n = 1$ or $a_n = \alpha$ appropriately, we can avoid exact cancellation of the residual $r_n$. Consequently, the residual can be made strictly positive but arbitrarily small, satisfying $0 < |x - X| < \epsilon$.

Step 5: Conclusion.

The greedy procedure produces a decimal representation using digits ${0,1,\alpha}$ such that the approximation to $x$ is within $\epsilon$ but not equal to $x$. Therefore, for any real number $x$ and any $\epsilon > 0$, there exists a representation

$X = \sum_{k \ge 0} a_k 10^k, \quad a_k \in {0,1,\alpha},$

satisfying $0 < |x - X| < \epsilon$.

This completes the proof.

∎