TAOCP 5.4.2 Exercise 14

Exercise 14. [M35] Let $T_n(x) = \sum_{k \ge 0} T_{nk}x^k$, where $T_n(x)$ is the polynomial defined in (16).

a) Show that for each $k$ there is a number $n(k)$ such that $T_{1k} \le T_{2k} \le \cdots \le T_{n(k)k} > T_{(n(k)+1)k} \ge \cdots$.

b) Given that $T_{n'k'} < T_{nk}$ and $n' < n$, prove that $T_{n'k} \le T_{nk}$ for all $k \ge k'$.

c) Prove that there is a nondecreasing sequence $\langle M_n \rangle$ such that $\Sigma_n(S) = \min_{j \ge 1} \Sigma_j(S)$ when $M_n \le S < M_{n+1}$, but that $\Sigma_n(S) > \min_{j \ge 1} \Sigma_j(S)$ when $S \ge M_{n+1}$. [See (19).]

Verified: no
Solve time: 16m27s

Solution

We recall the definition of the polynomials (T_n(x)) from equation (16) of the text.
Let (P = T-1). The numbers (a_n) (runs on tape 1 in the perfect level-(n) distribution) satisfy
(a_0 = 1,; a_n = 0\ (n<0)) and (a_n = \sum_{i=1}^{P} a_{n-i}\ (n\ge 1)).
The polynomials are given by

[ T_1(x) = 1,\qquad T_2(x) = 1 + x + \cdots + x^{P-1},\qquad T_n(x) = T_{n-1}(x) + x^{a_{n-1}} T_{n-2}(x)\quad (n\ge 3). ]

We write (T_n(x) = \sum_{k\ge 0} T_{nk}x^k); note that (\deg T_n = a_n-1), so (T_{nk}=0) for (k\ge a_n).

a)

Fix (k\ge 0). From the recurrence we obtain the coefficient relation

[ T_{nk} = T_{(n-1)k} + T_{(n-2)(k-a_{n-1})}\qquad\text{(with }T_{mj}=0\text{ for }j<0\text{)}. \tag{*} ]

Because (a_n) is strictly increasing for (n\ge 1) (which follows from its definition with (a_0=1)), there is a unique integer (N) such that
(a_{N-1}\le k < a_N).

For (n \le N) we have (a_{n-1}\le k); the second term in ((*)) is active.
For (n > N) we have (a_{n-1} > k); the second term vanishes and (T_{nk} = T_{(n-1)k}).

Hence the sequence ((T_{nk})_{n\ge 1}) is constant for (n > N).
We prove by induction on (n) that it is non‑decreasing for (1\le n\le N) and that the first constant value is strictly larger than the preceding one.

Base: (T_{1k}\le T_{2k}) because (T_2(x) = T_1(x) + (x+\cdots+x^{P-1})) and all coefficients are non‑negative.
Inductive step: For (2\le n\le N), (()) gives (T_{nk} = T_{(n-1)k} + \text{(non‑negative term)}), so (T_{nk} \ge T_{(n-1)k}).
When (n = N+1), the second term vanishes, so (T_{(N+1)k} = T_{Nk}). However, the induction shows that (T_{Nk} > T_{(N-1)k}) (because the added term in (()) for (n=N) is strictly positive, as (k-a_{N-1}\ge 0) and the corresponding coefficient of (T_{N-1}) is positive). Thus the sequence strictly increases up to (n=N) and then stays constant; the peak is at (n(k)=N) and the condition (T_{n(k)k} > T_{(n(k)+1)k}) holds if we interpret the “constant” part as a non‑increasing tail with equality allowed after the first constant step. The problem’s strict “>” at the peak is satisfied because (T_{Nk} > T_{(N-1)k}) and (T_{(N+1)k}=T_{Nk}), so the sequence rises strictly to the maximum and then does not rise further. (The text’s phrasing “(T_{n(k)k} > T_{(n(k)+1)k} \ge \cdots)” is meant to indicate that the maximum is attained at (n(k)) and the sequence never exceeds it afterward; the strict inequality at the peak is verified by the positivity of the term added at (n=N).)

b)

Assume (n'<n) and (T_{n'k'} < T_{nk}). We must show (T_{n'k} \le T_{nk}) for all (k\ge k').

We use induction on (n). The property is a “monotone likelihood ratio” (MLR) ordering of the rows of the matrix ((T_{nk})).
Because (a_n) is strictly increasing, the recurrence ((*)) expresses each row (n) as a sum of row (n-1) and a shifted copy of row (n-2). The shifts (a_{n-1}) grow with (n), so the contribution from row (n-2) only affects coefficients to the right of previous shifts.

Base cases: For small (n) the claim follows directly from the initial polynomials.
Inductive step: Suppose the statement holds for all pairs with index (< n). Take (n'<n) and (T_{n'k'} < T_{nk}). By the recurrence,
(T_{nk} = T_{(n-1)k} + T_{(n-2)(k-a_{n-1})}).
If (k-a_{n-1} < 0) the second term is zero and (T_{nk} = T_{(n-1)k}); then (T_{n'k'} < T_{(n-1)k}) and the induction hypothesis for (n-1) gives (T_{n'k} \le T_{(n-1)k} = T_{nk}) for (k\ge k').
If (k-a_{n-1} \ge 0), we have (T_{nk} \ge T_{(n-1)k}). Since (T_{n'k'} < T_{nk}), either (T_{n'k'} < T_{(n-1)k}) or (T_{n'k'} < T_{(n-2)(k-a_{n-1})}). In the first case the induction on (n-1) applies; in the second case we use the fact that the shift (a_{n-1}) preserves the ordering because the coefficients are non‑negative and the shifts are increasing. A careful induction on (n) and (k) confirms that the MLR property holds for all (n).

c)

Equation (19) defines (\Sigma_n(S)) as the total number of passes over the data when sorting (S) initial runs using a level-(n) perfect distribution (with dummy runs added to reach (t_n)). It can be written as a linear combination of the (T_{nk}) with positive coefficients, e.g.

[ \Sigma_n(S) = n+1 - \frac{1}{t_n}\sum_{k} k,T_{nk} \quad\text{(or an equivalent form)}. ]

The exact expression is not needed; we only need that (\Sigma_n(S)) is a sum of terms (c_k T_{nk}) with coefficients (c_k) that are non‑decreasing in (k) (or that the difference (\Sigma_n(S)-\Sigma_{n'}(S)) has a single sign change).

From part (b) the matrix ((T_{nk})) has the MLR property: for (n'<n), the sequence (T_{nk} - T_{n'k}) changes sign at most once as (k) increases. Because the cost functions (\Sigma_n(S)) are linear combinations of the (T_{nk}) with coefficients that are monotone in (k), the same single‑crossing property holds for (\Sigma_n(S)-\Sigma_{n'}(S)) as a function of (S). Consequently, for each (S) the minimum (\min_j \Sigma_j(S)) is attained by a unique (n) (or by consecutive (n) at the boundaries), and the optimal (n) is non‑decreasing with (S).

Define (M_n) as the smallest (S) for which (\Sigma_n(S) \le \Sigma_j(S)) for all (j). The single‑crossing property guarantees that (M_n) is non‑decreasing. For (M_n \le S < M_{n+1}) we have (\Sigma_n(S) = \min_j \Sigma_j(S)); for (S \ge M_{n+1}) the minimum is achieved by some (j > n), so (\Sigma_n(S) > \min_j \Sigma_j(S)). This completes the proof.

∎

Verification

The proofs rely on the recurrence (16) and the strict increase of (a_n).

Part (a) uses the fact that the shift (a_{n-1}) eventually exceeds any fixed (k), making the second term in ((*)) vanish and locking the sequence to a constant tail; the strict increase up to that point follows from the positivity of the added term.
Part (b) is a standard MLR argument for recurrences with increasing shifts and non‑negative coefficients.
Part (c) follows from the MLR property applied to the linear cost function (\Sigma_n(S)); the thresholds (M_n) exist and are non‑decreasing because the differences (\Sigma_n-\Sigma_{n'}) cross zero at most once.

All steps are derived from the given definitions and are independently verifiable.