TAOCP 4.1 Exercise 33

Section 4.1: Positional Number Systems

Exercise 33. [M40] (D. A. Klarner.) Let $D$ be any set of integers, let $b$ be any positive integer, and let $k_n$ be the number of different integers that can be written as $n$-digit numbers $(a_{n-1}\ldots a_1 a_0)_b$ to base $b$ with digits $a_i$ in $D$. Prove that the sequence $(k_n)$ satisfies a linear recurrence of the generating function algorithm by showing that $k_n$ is a Fibonacci number in the case $b = 3$ and $D = {-1, 0, 3}$.

Verified: no
Solve time: 7m10s

---

Exercise 4.1.33 [M40] (D. A. Klarner)

Let $D$ be any set of integers, let $b$ be any positive integer, and let $k_n$ be the number of distinct integers representable as $n$-digit numbers $(a_{n-1}\ldots a_0)_b$ with digits $a_i\in D$. Prove that $(k_n)$ satisfies a linear recurrence, and show that in the case $b=3$, $D={-1,0,3}$, $k_n$ is a Fibonacci number.

Solution

1. General case: $D$ arbitrary, $b$ arbitrary

Define

$$ S_n = \left{\sum_{i=0}^{n-1} a_i b^i : a_i \in D \right},\qquad k_n = |S_n|. $$

We aim to show that $(k_n)$ satisfies a linear recurrence.

Step 1.1: Recursive structure of $S_n$

Observe that adding a new digit in the most significant position yields

$$ S_{n+1} = \bigcup_{d \in D} \left{ d b^n + x : x \in S_n \right} = \bigcup_{d\in D} (S_n + d, b^n). $$

This expresses $S_{n+1}$ in terms of $S_n$.

Step 1.2: Reduction to a finite state system

Let

$$ m = \min D, \qquad M = \max D, \qquad C = M-m. $$

Then

$$ m \frac{b^n-1}{b-1} \le x \le M \frac{b^n-1}{b-1},\quad x\in S_n, $$

so the elements of $S_n$ lie in an interval of length

$$ L_n = M \frac{b^n-1}{b-1} - m \frac{b^n-1}{b-1} = C\frac{b^n-1}{b-1}. $$

Define the indicator function

$$ \varepsilon_n(t) = \begin{cases} 1,& t \in S_n,\ 0,& t \notin S_n. \end{cases} $$

Then $\varepsilon_{n+1}$ is determined from $\varepsilon_n$ via

$$ \varepsilon_{n+1}(x) = \sum_{d\in D} \varepsilon_n(x - d b^n), $$

where the sum is interpreted in ${0,1}$ (membership in $S_{n+1}$).

Step 1.3: Finiteness of the relative configuration

Introduce the shifted sets

$$ T_n = S_n - m \frac{b^n-1}{b-1}. $$

Then $0 \le t \le C (b^n-1)/(b-1)$ for all $t\in T_n$. For fixed $C$ and $b$, there are only finitely many possible configurations of the membership pattern of consecutive integers modulo $b^n$, because the union in Step 1.2 only shifts existing elements by finitely many differences $d b^n$ and takes their union.

Formally, define a state as the pattern of occupied positions relative to the minimal element modulo $b^n$. There are finitely many such states because:

1. Each element in $S_n$ is in an interval of length $C (b^n-1)/(b-1)$.
2. Each $S_{n+1}$ is obtained by translating $S_n$ by finitely many values $d b^n$, $d\in D$.
3. Therefore the membership pattern of the shifted set can take only finitely many forms.

This defines a finite state system with a transfer rule

$$ \text{state of } S_{n+1} = f(\text{state of } S_n) $$

where $f$ depends only on $b$ and $D$.

Step 1.4: Linear recurrence from the generating function algorithm

Let

$$ F(z) = \sum_{x\in S_n} z^x. $$

The vector of generating functions for all possible finite states evolves linearly under the transfer rule, producing a finite transfer matrix $T$ such that

$$ \mathbf{v}_{n+1} = T \mathbf{v}_n, $$

where $\mathbf{v}_n$ is the vector encoding which states occur at step $n$. The sequence

$$ k_n = |S_n| = \sum \mathbf{v}_n $$

is thus a linear combination of components of $T^n \mathbf{v}_0$. Standard linear-algebra facts imply that $(k_n)$ satisfies a linear recurrence with constant coefficients.

Hence, for arbitrary $D$ and $b$, the sequence $(k_n)$ satisfies a linear recurrence.

2. Special case: $b=3$, $D={-1,0,3}$

Let $S_n$ and $k_n = |S_n|$ be as above. Then

$$ S_{n+1} = (S_n - 3^n) \cup S_n \cup (S_n + 3^{, n+1}). $$

Define

$$ m_n = \min S_n, \qquad M_n = \max S_n. $$

Choosing all digits equal to $-1$ gives

$$ m_n = -\sum_{j=0}^{n-1} 3^j = -\frac{3^n-1}{2}, $$

and all digits equal to $3$ gives

$$ M_n = 3 \sum_{j=0}^{n-1} 3^j = \frac{3(3^n-1)}{2}. $$

Step 2.1: Disjointness relations

We have

$$ M_n - 3^{n+1} = \frac{3(3^n-1)}{2} - 3^{n+1} = -\frac{3^n + 3}{2} < m_n, $$

hence

$$ S_n \cap (S_n + 3^{n+1}) = \varnothing. $$

Also

$$ (S_{n-1} - 3^n) \cap S_n = \varnothing. $$

Moreover,

$$ (S_n - 3^n) \cap S_n $$