TAOCP 4.1 Exercise 30
**Exercise 4.
Section 4.1: Positional Number Systems
Exercise 30. [**] $[M39]$ (N. G. de Bruijn.) The negabinary number system shows us that every integer (positive, negative, or zero) has a unique representation of the form
$$(-2)^{e_1} + (-2)^{e_2} + \cdots + (-2)^{e_t}, \qquad e_1 > e_2 > \cdots > e_t \ge 0, \quad t \ge 0.$$
The purpose of this exercise is to explore generalizations of this phenomenon.
a) Let $b_0, b_1, b_2, \ldots$ be a sequence of integers such that every integer $n$ has a unique representation of the form
$$n = b_{e_1} + b_{e_2} + \cdots + b_{e_t}, \qquad e_1 > e_2 > \cdots > e_t \ge 0, \quad t \ge 0.$$
(Such a sequence $(b_n)$ is called a "binary basis.") Show that there is an index $j$ such that $b_j$ is odd, but $b_k$ is even for all $k \ne j$.
b) Prove that a binary basis $(b_n)$ can always be rearranged into the form $d_0, 2d_1, 4d_2, \ldots = (2^n d_n)$, where each $d_k$ is odd.
c) If each of $d_0, d_1, d_2, \ldots$ in (b) is $\pm 1$, prove that $(b_n)$ is a binary basis if and only if there are infinitely many $+1$'s and infinitely many $-1$'s.
d) Prove that $13, -7, -13\cdot 2, 7\cdot 2^2, -13\cdot 2^3, 7\cdot 2^4, -13\cdot 2^5, \ldots$ is a binary basis, and find the representation of $n = 1$.
Verified: no
Solve time: 16m40s
Exercise 4.1.30 [M39]
Let a binary basis be a sequence of integers $(b_n)_{n \ge 0}$ such that every integer $n$ has a unique representation of the form
$$ n = b_{e_1} + b_{e_2} + \cdots + b_{e_t}, \qquad e_1 > e_2 > \cdots > e_t \ge 0, \quad t \ge 0. $$
We study structural properties of binary bases and specific examples.
(a) Exactly one $b_j$ is odd.
Consider the representation of integers modulo $2$. Suppose first that all $b_k$ are even. Then every sum of distinct $b_k$ is even, so no odd integer could be represented, contradicting the definition of a binary basis. Therefore at least one $b_j$ is odd.
Suppose now that two distinct elements, $b_j$ and $b_k$, are odd. Consider the integer $0$. Its representation is the empty sum. Then the sum $b_j + b_k$ is even modulo $2$ because the sum of two odd numbers is even. Therefore the parity of the representation does not uniquely distinguish $0$ from $b_j + b_k$, contradicting uniqueness. Hence there cannot be more than one odd element.
We conclude that exactly one $b_j$ is odd, and all other $b_k$ with $k \ne j$ are even.
∎
(b) Reduction to the form $b_n = 2^n d_n$ with $d_n$ odd.
Let $(b_n)$ be a binary basis. By part (a), there exists a unique odd element; denote it $d_0$. Remove $d_0$ from the sequence, and let the remaining elements be divided by $2$. Denote the resulting sequence as $b'_0, b'_1, \dots$ where $b'_k = b_k/2$.
Claim: $(b'_k)$ is again a binary basis for all integers.
Proof of claim: Let $m$ be any integer. Consider the original basis $(b_n)$:
- If $m$ has a representation that includes $d_0$, write $m = d_0 + \sum_{k} b_k \varepsilon_k$. Then $(m - d_0)/2 = \sum_k b'_k \varepsilon_k$ is a representation of $(m - d_0)/2$ in $(b'_k)$.
- If $m$ has a representation that excludes $d_0$, write $m = \sum_k b_k \varepsilon_k$. Then $m/2 = \sum_k b'_k \varepsilon_k$ is a representation of $m/2$ in $(b'_k)$.
Uniqueness is preserved: if two distinct representations of some $m$ existed in $(b'_k)$, they would lift to two distinct representations of either $2m$ or $2m + d_0$ in $(b_n)$, contradicting uniqueness.
Thus $(b'_k)$ is a binary basis.
Applying this argument recursively, we obtain a rearrangement of $(b_n)$ into the form
$$ b_0 = d_0, \quad b_1 = 2 d_1, \quad b_2 = 4 d_2, \ \dots, \quad b_n = 2^n d_n, $$
where each $d_n$ is odd.
∎
(c) Characterization when $d_n = \pm 1$.
Suppose $b_n = 2^n d_n$ with $d_n \in {+1, -1}$ for all $n$.
Necessity:
Assume $(b_n)$ is a binary basis. Suppose there are only finitely many $d_n = +1$. Then there exists $N$ such that $d_n = -1$ for all $n > N$. Consider the sum of any subset of indices $> N$. All terms are negative. The maximal positive integer representable is therefore
$$ \sum_{n=0}^{N} 2^n |d_n| < \infty, $$
so some sufficiently large positive integer cannot be represented. Similarly, if only finitely many $d_n = -1$, some sufficiently large negative integer cannot be represented. Hence there must be infinitely many $+1$'s and infinitely many $-1$'s.
Sufficiency:
Assume infinitely many $d_n = +1$ and infinitely many $d_n = -1$. We show that every integer $n$ has a unique finite representation.
We construct the representation recursively. Define a sequence $(n_k)$ by:
$$ n_0 = n, \quad n_{k+1} = \frac{n_k - \varepsilon_k d_k}{2}, $$
where $\varepsilon_k \in {0,1}$ is chosen such that $n_k - \varepsilon_k d_k \equiv 0 \pmod 2$. This is always possible because $d_k$ is odd.
Termination: Since infinitely many $d_k$ are $+1$ and infinitely many are $-1$, for sufficiently large $k$, $2^k d_k$ dominates $n_k$, allowing a choice of $\varepsilon_k$ that decreases $|n_k|$. More formally, if $|n_k| \le 2^k$, choose $\varepsilon_k$ to cancel the sign of $n_k$ if $d_k$ has the opposite sign. The process ensures that eventually $n_m = 0$, giving a finite sum.
Uniqueness: Suppose two distinct representations exist. Let $m$ be the largest index at which they differ. Then their difference is
$$ \pm 2^m + \sum_{k < m} c_k 2^k, \quad c_k \in {-1,0,1}. $$
This number is odd and divisible by $2^m$, a contradiction. Hence the representation is unique.
∎
(d) Explicit binary basis and representation of $n=1$.
Consider the sequence
$$ b_0 = 13, \quad b_1 = -7, \quad b_2 = -13\cdot 2, \quad b_3 = 7\cdot 2^2, \quad b_4 = -13\cdot 2^3, \quad b_5 = 7\cdot 2^4, \dots $$
with pattern
$$ b_{2k} = (-13)\cdot 2^{k}, \quad b_{2k+1} = 7 \cdot 2^k \text{ for } k \ge 0, \text{ and alternating signs as above.} $$
Write $b_n = 2^n d_n$:
$$ d_0 = 13, \quad d_1 = -7, \quad d_2 = -13, \quad d_3 = 7, \quad d_4 = -13, \quad d_5 = 7, \dots $$
Then $d_n \in { \pm 13, \pm 7 }$ and alternate infinitely often in sign.
By part (c), this sequence is a binary basis because infinitely many $+d$ and $-d$ values occur. The powers of $2$ ensure uniqueness of subset sums.
Representation of $n=1$:
We seek integers $\varepsilon_k \in {0,1}$ such that
$$ 1 = \sum_{k=0}^\infty \varepsilon_k b_k. $$
Compute recursively using $n_0 = 1$:
- $b_0 = 13$. $n_0 - \varepsilon_0 b_0 \equiv 0 \pmod 2$. $13 \equiv 1 \pmod 2$, so choose $\varepsilon_0 = 0$. Then $n_1 = n_0/2 = 1/2$ (non-integer).
To get an integer, adjust by choosing $\varepsilon_1 = 1$ for $b_1 = -7$: $n_1 = (1 - (-7))/2 = 4$.
Next, $