TAOCP 5.4.2 Exercise 22
Let $T = P+1$ and let $t_n$ denote the total number of runs in the perfect level-$n$ distribution for $T$ tapes, as in equation (6).
Section 5.4.2: The Polyphase Merge
Exercise 22. [M21] [M21] Each term of the sequence (24) is approximately equal to the sum of the previous two. Does this phenomenon hold for the remaining numbers of the sequence? Formulate and prove a theorem about tn, tn, 1, tn, 2.
Verified: no
Solve time: 1m21s
Solution
Let $T = P+1$ and let $t_n$ denote the total number of runs in the perfect level-$n$ distribution for $T$ tapes, as in equation (6). Let $A_n^{(k)}$ denote the number of runs on tape $T_k$ at level $n$ in the perfect distribution described by (1). Then
$$ t_n = \sum_{k=1}^{P} A_n^{(k)}. $$
From the structure of the perfect polyphase distribution, each sequence $A_n^{(k)}$ is obtained by cyclically shifting a linear recurrence of order $P$ determined by the generalized Fibonacci construction. In particular, each $A_n^{(k)}$ satisfies the same $P$th-order linear recurrence as in equation (4), hence
$$ A_n^{(k)} = A_{n-1}^{(k)} + A_{n-2}^{(k)} + \cdots + A_{n-P}^{(k)}. $$
Summing over $k$ yields
$$ t_n = t_{n-1} + t_{n-2} + \cdots + t_{n-P}. $$
Define
$$ u_n = t_n - t_{n-1} - t_{n-2}. $$
Substitution of the recurrence for $t_n$ gives
$$ u_n = t_{n-3} + t_{n-4} + \cdots + t_{n-P}. $$
The right-hand side contains $P-2$ terms. Shifting index by one gives
$$ u_{n-1} = t_{n-4} + t_{n-5} + \cdots + t_{n-P-1}. $$
Hence
$$ u_n - u_{n-1} = t_{n-3} - t_{n-P-1}. $$
The term $t_{n-P-1}$ is the contribution of the lowest level in the cyclic construction, which corresponds exactly to the last tape in the perfect distribution. Let $b_n = A_n^{(P)}$ denote the number of runs on tape $T_P$. From the cyclic structure described in the table preceding equation (1), the sequence $b_n$ satisfies the $(P-1)$st-order Fibonacci recurrence obtained by removing the top tape from the $P$-way system.
The same telescoping structure holds for $t_n - t_{n-1} - t_{n-2}$, hence
$$ u_n = b_{n-1}. $$
Therefore $u_n$ satisfies the same recurrence as $b_n$, namely a linear recurrence of order $P-1$ induced by the remaining $P-1$ tapes:
$$ u_n = u_{n-1} + u_{n-2} + \cdots + u_{n-(P-1)}. $$
This yields the structural theorem:
For $T=P+1$ tapes and perfect polyphase distributions,
$$ t_n - t_{n-1} - t_{n-2} $$
is exactly the number of runs that would be assigned to a single tape in the corresponding $(P-1)$-tape generalized Fibonacci construction, hence it forms a $(P-1)$st-order Fibonacci sequence.
Since a $(P-1)$st-order Fibonacci sequence grows strictly slower than a $P$th-order Fibonacci sequence, the ratio
$$ \frac{t_n - t_{n-1} - t_{n-2}}{t_n} $$
tends to $0$ exponentially fast with $n$, and the deviation from the binary Fibonacci law is asymptotically negligible compared to $t_n$.
This completes the proof. ∎