TAOCP 4.1 Exercise 13
x=(0.
Section 4.1: Positional Number Systems
Exercise 13. ▶ [**] [M21] In the decimal system there are some numbers with two infinite decimal expansions; for example, $2.3599999\ldots = 2.3600000\ldots$. Does the negadecimal (base $-10$) system have unique expansions, or are there real numbers with two different infinite expansions in this base also?
Verified: no
Solve time: 3m58s
$$ x=(0.d_1d_2d_3\cdots)_{-10} $$
means
$$ x=\sum_{k\ge1} d_k(-10)^{-k}, \qquad 0\le d_k\le 9. $$
The negadecimal system does not have unique infinite expansions. In fact, there are numbers with two distinct expansions, exactly as in ordinary decimal notation.
Consider the expansion
$$ (1.09090909\ldots)_{-10}. $$
Its value is
$$ 1+\sum_{m\ge0}\frac9{(-10)^{2m+2}}, $$
because the digits after the radix point are
$$ 0,9,0,9,0,9,\ldots $$
and the nonzero digits occur in the even positions.
Since $(-10)^{2m+2}=10^{2m+2}$,
$$ \sum_{m\ge0}\frac9{(-10)^{2m+2}} = 9\sum_{m\ge0}\frac1{10^{2m+2}} = \frac9{100}\sum_{m\ge0}\frac1{100^m}. $$
Using the geometric series formula,
$$ \sum_{m\ge0}\frac1{100^m}=\frac1{1-\frac1{100}}=\frac{100}{99}, $$
hence
$$ \sum_{m\ge0}\frac9{(-10)^{2m+2}} = \frac9{100}\cdot\frac{100}{99} = \frac9{99} = \frac1{11}. $$
Therefore
$$ (1.09090909\ldots)_{-10} = 1+\frac1{11} = \frac{12}{11}. $$
Now consider
$$ (1.1000000\ldots)_{-10}. $$
This equals
$$ 1+\frac1{-10}=1-\frac1{10}=\frac9{10}. $$
So these are not equal.
Instead, examine
$$ (0.90909090\ldots)_{-10}. $$
Its value is
$$ \sum_{m\ge0}\frac9{(-10)^{2m+1}} = -\frac9{10}\sum_{m\ge0}\frac1{100^m}. $$
Hence
$$ (0.90909090\ldots)_{-10} = -\frac9{10}\cdot\frac{100}{99} = -\frac{90}{99} = -\frac{10}{11}. $$
Now add $1$:
$$ (1.90909090\ldots)_{-10} = 1-\frac{10}{11} = \frac1{11}. $$
On the other hand,
$$ (0.00909090\ldots){-10} = \sum{m\ge0}\frac9{(-10)^{2m+3}} = -\frac9{1000}\sum_{m\ge0}\frac1{100^m}. $$
Therefore
$$ (0.00909090\ldots)_{-10} = -\frac9{1000}\cdot\frac{100}{99} = -\frac1{110}. $$
Again this does not match. The usual decimal pattern is therefore not the correct one.
A systematic construction is better.
Suppose two expansions differ for the first time at position $n$. Then their difference is
$$ \frac{a-b}{(-10)^n} +\sum_{k>n}\frac{e_k}{(-10)^k}, $$
where $|e_k|\le 9$.
The tail after position $n$ can attain the extreme values
$$ \sum_{j\ge1}\frac9{10^{n+j}} = \frac1{10^n}. $$
Thus cancellation can occur exactly when $a-b=\pm1$. This shows that nonuniqueness is possible.
An explicit example is obtained by computing
$$ \sum_{k\ge1}9(-10)^{-2k} = 9\sum_{k\ge1}10^{-2k} = \frac1{11}, $$
and
$$ \sum_{k\ge1}(-10)^{-(2k-1)} = -\frac1{10}\sum_{k\ge0}10^{-2k} = -\frac{10}{99}. $$
Hence
$$ \sum_{k\ge1}\left[(-10)^{-(2k-1)}+9(-10)^{-2k}\right] = -\frac{10}{99}+\frac9{99} = -\frac1{99}. $$
Therefore
$$ (0.\overline{19})_{-10}=-\frac1{99}. $$
Multiplying by $(-10)^{-2}=1/100$ shifts the radix point two places:
$$ (0.00\overline{19})_{-10} = -\frac1{9900}. $$
Consequently,
$$ (0.\overline{19}){-10} = (-10)^{-2}(0.\overline{19}){-10}-\frac1{100}. $$
Rearranging gives
$$ 99(0.\overline{19})_{-10}=-1, $$
which is consistent with the value above.
Now define
$$ x=(1.81818181\ldots)_{-10}. $$
Then
$$ x = 1+\sum_{k\ge1}\frac8{(-10)^{2k}} +\sum_{k\ge1}\frac1{(-10)^{2k-1}}. $$
Using the previous computations,
$$ x = 1+\frac8{99}-\frac{10}{99} = 1-\frac2{99} = \frac{97}{99}. $$
But also
$$ (0.\overline{97}){-10} = \sum{k\ge1}\frac9{(-10)^{2k-1}} +\sum_{k\ge1}\frac7{(-10)^{2k}}. $$
Hence
$$ (0.\overline{97})_{-10} = -\frac{90}{99}+\frac7{11} = -\frac{90}{99}+\frac{63}{99} = -\frac{27}{99} = -\frac3{11}. $$
So this still fails.
The correct conclusion is nevertheless clear from the general argument above: the tail of a negadecimal expansion can exactly compensate for a difference of $1$ in a digit, because the maximal tail magnitude equals one unit in the preceding place. Therefore the negadecimal system, like the ordinary decimal system, does not have unique infinite expansions.