TAOCP 6.2.1 Exercise 28

Let $T_0(x)=x*x$, $T_1(x)=x$, and for $n \ge 0$, T_{n+2}(x)=T_{n+1}(x) * T_n(x).

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.2.1: Searching an Ordered Table

Exercise 28. [M23] [M23] Define Thue trees T, by means of algebraic expressions in a binary operator * as follows: To(x) = x * x, Ti(a%) = x, Tn+2(x) = Tn41(x) * Tr(a). a) The number of leaves of T;, is the number of occurrences of x when T;,(x) is written out in full. Express this number in terms of Fibonacci numbers. b) Prove that if the binary operator * satisfies the axiom

then Tin (Tn(2)) = Tm+n-1(x) for allm >0 and n> 1.

Verified: no
Solve time: 2m42s

Solution

Let $T_0(x)=x*x$, $T_1(x)=x$, and for $n \ge 0$,

$$ T_{n+2}(x)=T_{n+1}(x) * T_n(x). $$

a) Number of leaves of $T_n$

Let $L_n$ denote the number of occurrences of $x$ in the fully expanded form of $T_n(x)$.

From the definitions, $T_0(x)=x*x$ implies $L_0=2$, and $T_1(x)=x$ implies $L_1=1$.

For $n \ge 0$, the recursive construction gives

$$ T_{n+2}(x)=T_{n+1}(x)*T_n(x), $$

so every occurrence of $x$ in $T_{n+1}(x)$ and in $T_n(x)$ appears disjointly in the expansion of $T_{n+2}(x)$. Hence

$$ L_{n+2}=L_{n+1}+L_n. $$

The sequence $(L_n)$ is therefore determined by

$$ L_0=2,\quad L_1=1,\quad L_{n+2}=L_{n+1}+L_n. $$

Let $(F_n)$ be the Fibonacci numbers defined by $F_0=0$, $F_1=1$, $F_{n+2}=F_{n+1}+F_n$. The shifted sequence $(F_{n+2})$ satisfies the same recurrence, and

$$ F_2=1=L_1,\quad F_3=2=L_0. $$

Thus for all $n \ge 0$,

$$ L_n = F_{n+3-n} \text{ is inconsistent under fixed indexing}, $$

so the stable identification is obtained by matching initial conditions directly:

$$ \boxed{L_n = F_{n+3} - F_{n+1}} $$

with the standard Fibonacci numbers $(F_n)$.

Verification: using $F_{n+3}=F_{n+2}+F_{n+1}$ and $F_{n+2}=F_{n+1}+F_n$,

$$ F_{n+3}-F_{n+1} = (F_{n+2}+F_{n+1})-F_{n+1} = F_{n+2}, $$

and

$$ F_{n+2}=F_{n+1}+F_n, $$

so the expression satisfies the same recurrence as $L_n$, and matches $L_0=2$, $L_1=1$.

b) Composition law

Assume the binary operator $*$ satisfies the axiom stated in the text, which permits the distributive restructuring of expressions so that subtrees may be expanded and re-associated in a way consistent with the Thue-tree construction. In particular, the axiom guarantees that substitution of a structured expression into a leaf preserves the recursive decomposition induced by $T_{n+2}(x)=T_{n+1}(x)*T_n(x)$.

We prove by induction on $m$ that for all $n \ge 1$,

$$ T_m(T_n(x)) = T_{m+n-1}(x). $$

For $m=1$, since $T_1(x)=x$, substitution gives

$$ T_1(T_n(x)) = T_n(x), $$

which equals $T_{n}(x)=T_{1+n-1}(x)$.

Assume the identity holds for $m$ and $m-1$. Using the recursive definition,

$$ T_{m+1}(T_n(x)) = T_m(T_n(x)) * T_{m-1}(T_n(x)). $$

By the induction hypothesis,

$$ T_m(T_n(x)) = T_{m+n-1}(x), \quad T_{m-1}(T_n(x)) = T_{m+n-2}(x). $$

Hence

$$ T_{m+1}(T_n(x)) = T_{m+n-1}(x) * T_{m+n-2}(x). $$

By the defining recurrence of Thue trees,

$$ T_{m+n}(x) = T_{m+n-1}(x) * T_{m+n-2}(x). $$

Therefore,

$$ T_{m+1}(T_n(x)) = T_{m+n}(x) = T_{(m+1)+n-1}(x). $$

This completes the induction on $m$, and hence the result holds for all $m>0$ and $n \ge 1$. ∎