TAOCP 1.2.8 Exercise 35

Section 1.2.8: Fibonacci Numbers

Exercise 35. [M24] (A phi number system.) Consider real numbers written with the digits $0$ and $1$ using base $\phi$; thus $(100.1)_\phi = \phi^2 + \phi^{-1}$. Show that there are infinitely many ways to represent the number $1$; for example,

$$ 1 = (.11)\phi = (.011111\ldots)\phi. $$

But if we require that no two adjacent 1s occur and that the representation does not end with the infinite sequence $01010101\ldots$, then every nonnegative number has a unique representation. What are the representations of integers?

Verified: no
Solve time: -

Solution

We define a base-$\phi$ expansion of a real number $x \ge 0$ to be a formal series

$$ x = \sum_{k=-\infty}^{n} d_k \phi^k, $$

where each $d_k \in {0,1}$ and $n$ is an integer such that $d_n = 1$. Here, $\phi = \frac{1+\sqrt{5}}{2}$, and we adopt the usual convention that powers of $\phi$ can be negative. Observe that $\phi$ satisfies the quadratic equation

$$ \phi^2 = \phi + 1. \tag{1} $$

This allows us to replace any occurrence of $\phi^2$ by $\phi+1$, and conversely, to rewrite sums of the form $\phi+1$ as $\phi^2$. This replacement mechanism is the key to both the non-uniqueness and the uniqueness properties of the base-$\phi$ system.

Step 1: Infinitely many representations of $1$.

We first show that the number $1$ has infinitely many base-$\phi$ representations. The identity

$$ 1 = \phi^{-1} + \phi^{-2} \tag{2} $$

follows from solving Eq. (1) for $\phi^{-1}$:

$$ \phi^2 = \phi + 1 \implies 1 = \phi^2 - \phi = \phi(\phi-1) = \phi\cdot\phi^{-1} = 1. $$

To obtain alternative expansions, we repeatedly apply the substitution

$$ 1 = \phi^{-1} + \phi^{-2} = \phi^{-1} + (\phi^{-2} + 0\cdot\phi^{-3}) = \cdots, $$

or, more systematically, we use the recurrence

$$ (.1)\phi = \phi^{-1} = 1 - \phi^{-2} \implies 1 = (.11)\phi = (.0111\ldots)_\phi, $$

where each application replaces a block $1 = \phi^{-1} + \phi^{-2}$. Therefore, by iterating this process indefinitely, we generate infinitely many sequences of 0s and 1s representing $1$. Each new representation arises by "shifting a $1$ to the right" and filling with trailing $1$s, so there is no bound on the number of distinct expansions. This proves the first claim.

Step 2: Uniqueness under the non-adjacent-1s constraint.

We now impose the rule that no two adjacent 1s occur in the expansion, and the expansion does not end with the infinite sequence $010101\ldots$. Under these restrictions, every nonnegative real number has a unique base-$\phi$ representation.

The proof relies on greedy selection of the largest power of $\phi$ that does not exceed the number. Let $x \ge 0$ be given. We construct digits $d_n, d_{n-1}, \dots, d_0, d_{-1}, \dots$ recursively as follows:

Let $k$ be the largest integer such that $\phi^k \le x$. Set $d_k = 1$ and replace $x \leftarrow x - \phi^k$.
If $d_{k+1} = 1$, enforce $d_k = 0$ to avoid adjacent 1s.
Repeat for the remaining value of $x$, choosing the next largest $\phi^j \le x$ with $j < k-1$ (skip $k-1$ if $d_k=1$).
Continue recursively for all lower powers, including negative powers if necessary.

This algorithm is deterministic and produces a representation without adjacent 1s. To see that it is unique, suppose there were two distinct expansions satisfying the constraint:

$$ x = \sum_{k} d_k \phi^k = \sum_{k} d'_k \phi^k, $$

with $d_k \neq d'_k$ for some $k$. Let $n$ be the largest such index. Then the greedy choice guarantees that $d_n = 1$ and $d'_n = 0$, which implies

$$ \sum_{k<n} d_k \phi^k = x - \phi^n < \sum_{k<n} d'_k \phi^k \le x - \phi^n, $$

a contradiction. Hence no two distinct sequences satisfying the constraints can represent the same number. This completes the proof of uniqueness.

Step 3: Representations of integers.

Let $N$ be a nonnegative integer. We show that the unique base-$\phi$ expansion of $N$ is a finite sum of non-consecutive Fibonacci numbers, which are themselves powers of $\phi$ shifted by $-1$:

$$ F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}, \quad \hat{\phi} = 1-\phi. $$

By Eq. (15) from Section 1.2.8, $\hat{\phi}^n/\sqrt{5} < 1/2$ for all $n \ge 1$, so truncating powers of $\hat{\phi}$ does not affect integer values.

Let $k_1 > k_2 > \dots > k_r \ge 2$ be the indices of Fibonacci numbers in the Zeckendorf representation of $N$ (as in exercise 34):

$$ N = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, \qquad k_i \gg k_{i+1}. $$

Then the corresponding base-$\phi$ digits $d_{k_i-2} = 1$ and all other $d_j = 0$. No two adjacent digits are 1 because $k_i \gg k_{i+1}$, and all integers are obtained this way. For example:

$1 = F_2 = \phi^0 = (1)_\phi$,
$2 = F_3 = \phi^1 = (10)_\phi$,
$3 = F_4 = \phi^2 + \phi^0 = (101)_\phi$,
$4 = F_4 + F_2 = \phi^2 + \phi^0 = (101)_\phi$,
$5 = F_5 = \phi^3 + \phi^1 = (1001)_\phi$.

This establishes a one-to-one correspondence between integers and finite base-$\phi$ expansions with no adjacent 1s.

Step 4: Summary of integer representations.

Every nonnegative integer $N$ has a unique finite base-$\phi$ expansion without adjacent 1s, given by

$$ N = \sum_{i=0}^{m} d_i \phi^i, \quad d_i \in {0,1}, \quad d_i d_{i+1} = 0 \text{ for all } i. $$

The digits $d_i$ are obtained greedily by subtracting the largest possible power of $\phi$ at each step, and correspond exactly to the Zeckendorf representation of $N$ in terms of Fibonacci numbers.

This completes the solution.

∎