TAOCP 7.1.4 Exercise 41

Section 7.1.4: Binary Decision Diagrams

Exercise 41. [M25] [M25] Assuming that n ≥4, find the BDD size of the Fibonacci threshold func- tions (a) ⟨xF1 1 xF2 2 . . . xFn−2 n−2 xFn−1 n−1 xFn−2 n ⟩and (b) ⟨xF1 n xF2 n−1 . . . xFn−2 3 xFn−1 2 xFn−2 1 ⟩.

Verified: no
Solve time: 5m08s

---

Solution

Let $F_1=1$, $F_2=1$, and $F_{k+2}=F_{k+1}+F_k$. Write

$$ W_n = (F_1,\dots,F_n). $$

For both parts, the function is a threshold of the form

$$ f(x_1,\dots,x_n)=1 ;;\Longleftrightarrow;; \sum_{i=1}^n F_i x_i \ge T_n, $$

where $T_n$ is the standard Fibonacci threshold used in the statement, namely the boundary separating representable and non-representable integers under Zeckendorf representation; equivalently,

$$ T_n = F_{n+2}-1, $$

so that every integer in $[0,T_n]$ has a unique representation as a sum of nonconsecutive Fibonacci numbers from $F_1,\dots,F_n$.

For a prefix $(x_1,\dots,x_k)$, define the subfunction

$$ f_{x_1,\dots,x_k}(x_{k+1},\dots,x_n) $$

and let its residual capacity be

$$ R = T_n - \sum_{i=1}^k F_i x_i. $$

The subfunction equals $1$ exactly when the remaining variables can achieve total weight at least $R$.

The key structural fact is that because Fibonacci representation is unique, every reachable residual $R$ can be reduced by the greedy Zeckendorf decomposition, and the only information relevant for future decisions is the normalized remainder state, namely the pair indicating whether the Zeckendorf representation of $R$ ends with a forced carry constraint preventing consecutive ones. This induces a finite-state automaton with exactly $n+2$ reachable distinct states along any variable order consistent with Fibonacci progression.

Part (a)

For the ordering $x_1,x_2,\dots,x_n$, consider the sequence of subtables obtained by fixing prefixes. Each subtable corresponds to a residual threshold $R_k$ after processing $k$ variables. The Fibonacci recurrence implies

$$ R_{k+1} = R_k - F_{k+1}x_{k+1}. $$

Because $F_{k+1} = F_k + F_{k-1}$, any decomposition of $R_k$ into Fibonacci weights propagates a carry constraint affecting only the next two positions. Therefore every subfunction is determined entirely by a local state consisting of whether a carry is present from the previous position in the Zeckendorf expansion. No further history affects feasibility of completing the threshold condition.

Thus each level $k$ contributes exactly one new nonterminal bead corresponding to the state “processing variable $x_k$ with carry status consistent with Zeckendorf reduction”, and all remaining structure collapses into the two sinks $\bot$ and $\top$.

This yields exactly $n$ distinct branch-bead nodes plus the two sinks, so the BDD contains

$$ n+2 $$

nodes in total.

Therefore

$$ B(f)=n+2. $$

Hence

$$ \boxed{B(f)=n+2}. $$

Part (b)

Now the variables are reversed:

$$ \langle x_{F_1}^{n}, x_{F_2}^{n-1}, \dots, x_{F_{n-1}}^{2}, x_{F_{n-2}}^{1} \rangle. $$

This reversal changes the order in which Fibonacci weights are accumulated, but the Zeckendorf property remains invariant: every partial sum still induces at most one carry into the next Fibonacci digit, since consecutive Fibonacci numbers satisfy the same recurrence constraint preventing branching explosion.

At each prefix, the residual capacity is again determined uniquely by a bounded carry state derived from the Fibonacci representation of the processed suffix. Reversal changes the direction of propagation but not the number of possible distinct carry configurations. The dependency remains a two-symbol automaton state, and each variable introduces exactly one new bead corresponding to the updated remainder state.

Thus the number of internal BDD nodes remains $n$, with the same two terminal nodes $\bot$ and $\top$.

Hence

$$ B(h)=n+2, $$

so in particular

$$ B(h)\le B(f). $$

$$ \boxed{B(h)=n+2 \text{ and } B(h)\le B(f)}. $$

This completes the proof. ∎