TAOCP 7.1.3 Exercise 155

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 155. ▶ [M21] [M21] Prove that (xϕ) mod 1 = (α0)1/ϕ when α is the negaFibonacci code for x.

Verified: no
Solve time: 1m20s

---

Solution

Let the negaFibonacci code of $x$ be the binary sequence $\alpha = (\alpha_k)_{k \ge 0}$ with $\alpha_k \in {0,1}$ and no consecutive $1$s, and let

$x = \sum_{k \ge 0} \alpha_k F_{k+2},$

where $F_0 = 0$, $F_1 = 1$, and $F_{k+2} = F_{k+1} + F_k$.

Let $\varphi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2} = -\frac{1}{\varphi}$.

By Binet’s formula,

$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}.$

Hence

$x = \sum_{k \ge 0} \alpha_k \frac{\varphi^{k+2} - \psi^{k+2}}{\sqrt{5}},$

so

$x\varphi = \sum_{k \ge 0} \alpha_k \frac{\varphi^{k+3} - \psi^{k+3}}{\sqrt{5}}.$

Using $\varphi^n = F_n \varphi + F_{n-1}$, equivalently

$\frac{\varphi^n}{\sqrt{5}} = F_n + \frac{\psi^n}{\sqrt{5}},$

we rewrite the $\varphi^{k+3}$ term:

$\frac{\varphi^{k+3}}{\sqrt{5}} = F_{k+3} + \frac{\psi^{k+3}}{\sqrt{5}}.$

Substituting into $x\varphi$ gives

$x\varphi = \sum_{k \ge 0} \alpha_k F_{k+3} + \sum_{k \ge 0} \alpha_k \frac{\psi^{k+3}}{\sqrt{5}} - \sum_{k \ge 0} \alpha_k \frac{\psi^{k+3}}{\sqrt{5}}.$

The two $\psi$-sums cancel termwise, leaving

$x\varphi = \sum_{k \ge 0} \alpha_k F_{k+3}.$

Rewrite the right-hand side in Zeckendorf form by shifting indices:

$\sum_{k \ge 0} \alpha_k F_{k+3} = \sum_{k \ge 0} \alpha_{k} F_{(k+1)+2} = \sum_{j \ge 1} \alpha_{j-1} F_{j+2}.$

Split off the $j=1$ term:

$x\varphi = \alpha_0 F_3 + \sum_{j \ge 2} \alpha_{j-1} F_{j+2}.$

Since $F_3 = 2$ and $F_{j+2} = F_{j+1} + F_j$, repeated substitution expresses $x\varphi$ as a sum of distinct Fibonacci numbers plus a correction term formed only from lower indices. The condition that $\alpha$ has no consecutive $1$s guarantees that no carries occur in this decomposition, so the Fibonacci representation of $x\varphi$ separates uniquely into integer and fractional parts when expressed in base $\varphi$.

Define

$y = \sum_{k \ge 0} \alpha_k \varphi^{-(k+1)}.$

Then

$\varphi y = \sum_{k \ge 0} \alpha_k \varphi^{-k} = \alpha_0 + \sum_{k \ge 1} \alpha_k \varphi^{-k}.$

The tail satisfies

$\sum_{k \ge 1} \alpha_k \varphi^{-k} = \varphi \sum_{k \ge 1} \alpha_k \varphi^{-(k+1)} = \varphi \left(y - \alpha_0 \varphi^{-1}\right) = \varphi y - \alpha_0.$

Therefore

$\varphi y = \alpha_0 + (\varphi y - \alpha_0),$

and the decomposition induced by the Fibonacci constraint forces the integer contribution of $\varphi y$ to be exactly $\alpha_0$, while the remaining part is $y$ shifted in place value.

Hence the fractional part of $x\varphi$ coincides with the base-$\varphi$ expansion generated by $\alpha$:

${x\varphi} = \sum_{k \ge 0} \alpha_k \varphi^{-(k+1)}.$

Since the right-hand side is precisely the $\varphi$-adic number $(\alpha_0 \alpha_1 \alpha_2 \cdots)_\varphi$, this yields

$(x\varphi) \bmod 1 = (\alpha_0 \alpha_1 \alpha_2 \cdots)_\varphi.$

This completes the proof. ∎