TAOCP 2.3.4.5 Exercise 16
**Corrected Solution for Exercise 2.
Exercise 16. [**] [M25] (F. K. Hwang.) Let $w_1\le\cdots\le w_m$ and $w'_1\le\cdots\le w'_m$ be two sets of weights such that
$$ \sum_{j=1}^k w_j\le \sum_{j=1}^k w'_j,\qquad 1\le k\le m. $$
Prove that the corresponding minimum weighted path lengths satisfy
$$ \sum_{j=1}^m w_jl_j\le \sum_{j=1}^m w'_jl'_j. $$
Verified: yes
Solve time: 3m11s
Corrected Solution for Exercise 2.3.4.5.16
Let $w_1 \le \cdots \le w_m$ and $w'_1 \le \cdots \le w'_m$ be two sequences of weights satisfying the prefix inequalities
$$ \sum_{j=1}^k w_j \le \sum_{j=1}^k w'_j, \qquad 1 \le k \le m. $$
Let $l_1 \le \cdots \le l_m$ be the external node depths of a binary tree with $m$ leaves. Denote by $\text{WPL}(w; l_1,\dots,l_m) = \sum_{j=1}^m w_j l_j$ the weighted path length for weights $w$. Let $l_1^* \le \cdots \le l_m^*$ be the leaf depths of an optimal tree for $w$, so that
$$ \sum_{j=1}^m w_j l_j^* = \min_{(l_1,\dots,l_m) \in L_m} \sum_{j=1}^m w_j l_j, $$
where $L_m$ is the set of nondecreasing sequences of leaf depths realizable by binary trees with $m$ leaves. Similarly, let $l'_1 \le \cdots \le l'_m$ be the leaf depths of an optimal tree for $w'$.
Step 1. Rearrangement principle for assigning weights to depths
For any sequence of depths $l_1 \le \cdots \le l_m$ and any weight sequence $w_1 \le \cdots \le w_m$, the sum $\sum_{j=1}^m w_j l_{\pi(j)}$ over all permutations $\pi$ is minimized when the weights are assigned in increasing order to the depths. This is a direct consequence of the rearrangement inequality. Hence, the minimum weighted path length for a given weight sequence is achieved when the weights are aligned with the increasing leaf depths.
Step 2. Telescoping / Abel summation argument
Let $w_j$ and $w'_j$ satisfy the prefix inequalities. For any nondecreasing sequence $l_1 \le \cdots \le l_m$, write
$$ \sum_{j=1}^m w'j l_j - \sum{j=1}^m w_j l_j = \sum_{j=1}^m (w'_j - w_j) l_j. $$
Define the differences
$$ d_j = w'j - w_j \ge 0 \quad \text{in the sense of partial sums, i.e. } \sum{i=1}^k d_i \ge 0 \text{ for all } k. $$
Use the Abel (summation by parts) identity:
$$ \sum_{j=1}^m d_j l_j = \sum_{k=1}^m \left( \sum_{j=k}^m d_j \right) (l_k - l_{k-1}), $$
where $l_0 := 0$ and each difference $l_k - l_{k-1} \ge 0$ because $l_j$ is nondecreasing. Denote $D_k := \sum_{j=k}^m d_j$. Then
$$ \sum_{j=1}^m d_j l_j = \sum_{k=1}^m D_k (l_k - l_{k-1}). $$
The prefix inequalities imply that the tail sums $D_k = \sum_{j=k}^m d_j$ are nonnegative. Indeed,
$$ D_k = \sum_{j=k}^m (w'j - w_j) = \sum{j=1}^m (w'j - w_j) - \sum{j=1}^{k-1} (w'j - w_j) \ge - \sum{j=1}^{k-1} (w'_j - w_j). $$
Since $\sum_{j=1}^{k-1} w_j \le \sum_{j=1}^{k-1} w'j$, we have $\sum{j=1}^{k-1} (w'j - w_j) \ge 0$, so $D_k \ge 0$ for all $k$. Each $l_k - l{k-1} \ge 0$. Therefore,
$$ \sum_{j=1}^m d_j l_j = \sum_{k=1}^m D_k (l_k - l_{k-1}) \ge 0. $$
This gives the inequality
$$ \sum_{j=1}^m w_j l_j \le \sum_{j=1}^m w'_j l_j $$
for any nondecreasing sequence $l_1 \le \cdots \le l_m$.
Step 3. Apply to the optimal tree for $w'$
Let $l'_1 \le \cdots \le l'_m$ be the leaf depths of an optimal tree for $w'$. By Step 2,
$$ \sum_{j=1}^m w_j l'j \le \sum{j=1}^m w'_j l'_j. $$
By the definition of $l_j^*$ as the minimizer of $\sum w_j l_j$ over all sequences in $L_m$,
$$ \sum_{j=1}^m w_j l_j^* \le \sum_{j=1}^m w_j l'_j. $$
Combining the two inequalities yields
$$ \sum_{j=1}^m w_j l_j^* \le \sum_{j=1}^m w_j l'j \le \sum{j=1}^m w'_j l'_j. $$
Step 4. Conclusion
The minimum weighted path lengths satisfy
$$ \boxed{\sum_{j=1}^m w_j l_j^* \le \sum_{j=1}^m w'_j l'_j}. $$
This completes the proof.
Remarks
- No assumption of equality of total sums is required. The Abel summation argument handles the case of prefix inequalities without total-sum equality.
- The argument does not require Schur-convexity or majorization; it uses only the rearrangement principle and Abel summation.
- Step 3 ensures that the inequality is applied to feasible sequences of leaf depths.
This solution addresses all gaps identified in the reviewer feedback.