Every source-coding technique

Both directions go through the same picture: a complete D-ary tree, every internal node with exactly D children, where a codeword of length l corresponds to a node at depth l, and a prefix code corresponds to a set of nodes none of which is an ancestor of another.

Necessity: a prefix code forces the inequality. Suppose codewords of lengths l_1, \ldots, l_k form a prefix code, and let l_{\max} = \max_i l_i. Extend the tree down to depth l_{\max}. The node for codeword i, sitting at depth l_i, has exactly D^{l_{\max}-l_i} descendants at depth l_{\max} (every one of its subtree's leaves at that depth). Because the code is prefix — no codeword's node is an ancestor of another's — these descendant sets, for i=1,\ldots,k, are pairwise disjoint subsets of the D^{l_{\max}} nodes that exist at depth l_{\max}. A union of disjoint subsets can't exceed the whole: \sum_{i=1}^{k} D^{l_{\max}-l_i} \leq D^{l_{\max}}. Dividing both sides by D^{l_{\max}} gives \sum_i D^{-l_i} \leq 1.

Sufficiency: the inequality forces a prefix code to exist. Now assume \sum_{i=1}^k D^{-l_i} \leq 1 and relabel so l_1 \leq l_2 \leq \cdots \leq l_k. Build the code one codeword at a time, in this order, always assigning codeword i to some as-yet-unclaimed node at depth l_i — one neither equal to, nor a descendant of, any node already assigned to an earlier codeword. It has to be shown such a node is always available.

At step i, each earlier codeword j<i sits at depth l_j \leq l_i and blocks exactly D^{l_i - l_j} of the D^{l_i} nodes at depth l_i (its own descendants there). So the number of nodes at depth l_i still free is at least D^{l_i} - \sum_{j<i} D^{l_i - l_j}. Divide by D^{l_i}: this is positive exactly when \sum_{j<i} D^{-l_j} < 1. And indeed \sum_{j<i} D^{-l_j} = \sum_{j=1}^{k} D^{-l_j} - \sum_{j \geq i} D^{-l_j} \leq 1 - D^{-l_i} < 1, using the hypothesis for the first inequality and D^{-l_i}>0 for the second. So a free node at depth l_i always exists — assign codeword i to any one of them (say, the leftmost).

By construction, codeword i's node is never a descendant of an earlier codeword's node (that's exactly what "free" excluded), and since every later codeword is likewise assigned only to nodes that aren't descendants of any node claimed so far, codeword i's node never becomes an ancestor of a later codeword's node either. So no node in the final set is an ancestor of another: the resulting code is a genuine prefix code with exactly the lengths l_1,\ldots,l_k.

The bound is proved by turning it into an instance of Gibbs' inequality (relative entropy's non-negativity, 04-relative-entropy-and-cross-entropy §2), applied to the codeword lengths themselves rather than to two probability distributions in the usual sense.

Building a pseudo-distribution out of the lengths. Since C is uniquely decodable, the McMillan inequality applies to its lengths: \sum_x D^{-l(x)} \leq 1. Define q(x) := D^{-l(x)} \quad \text{for every outcome } x. Each q(x) is positive, and they sum to at most 1 — exactly the condition needed to run the Gibbs' inequality argument, whose own proof only ever used \sum_x Q(x) \leq 1, never that it equals 1 exactly (see that theorem's own "infinite case" step). So the same argument applies here even though \{q(x)\} is a genuine probability distribution only when C's lengths hit the Kraft bound with equality.

Rewriting the gap. Measuring entropy in D-ary units, H_D(X) := H(X)/\log_2 D = \sum_x p(x)\big({-\log_D p(x)}\big), the gap between expected length and this rescaled entropy is L - H_D(X) = \sum_x p(x)\,l(x) - \sum_x p(x)\big({-\log_D p(x)}\big) = \sum_x p(x)\Big(l(x) + \log_D p(x)\Big). Since l(x) = -\log_D D^{-l(x)} = -\log_D q(x), the bracketed term is -\log_D q(x) + \log_D p(x) = \log_D\!\dfrac{p(x)}{q(x)}, so L - H_D(X) = \sum_x p(x)\log_D\frac{p(x)}{q(x)}.

Applying Jensen to the log. This sum is non-negative by the same concave-Jensen step Gibbs' inequality itself runs: \log_D is concave, so for the random variable T = q(X)/p(X) evaluated under X's own distribution p, E_p\!\left[\log_D\frac{q(X)}{p(X)}\right] \leq \log_D E_p\!\left[\frac{q(X)}{p(X)}\right] = \log_D \sum_x p(x)\frac{q(x)}{p(x)} = \log_D \sum_x q(x) \leq \log_D 1 = 0, using \sum_x q(x)\leq 1 (McMillan) for the last step. The left side of that chain is exactly -\big(L-H_D(X)\big) (the same sum as above with the fraction flipped), so -(L - H_D(X)) \leq 0 \quad\Longleftrightarrow\quad L \geq H_D(X) = \frac{H(X)}{\log_2 D}.

Equality. Two inequalities were chained: the Jensen step, and \sum_x q(x) \leq 1. Equality throughout requires both individually tight.

• Jensen's inequality for the strictly concave \log_D is an equality only when T = q(X)/p(X) is constant across every outcome with p(x)>0 — say q(x) = c\,p(x) for some constant c.
• \sum_x q(x) \leq 1 is an equality only when C's lengths meet the Kraft bound exactly, \sum_x q(x) = 1.

Combining both: summing q(x)=c\,p(x) over all x gives 1 = c\cdot 1, so c=1, meaning q(x)=p(x) for every x — i.e. D^{-l(x)} = p(x), which rearranges to l(x) = -\log_D p(x). Since l(x) must be a positive integer, this equality case is only reachable when every -\log_D p(x) already happens to be a whole number; for any other source, L is strictly greater than H_D(X).

By induction on k, the alphabet size, built from two lemmas about what any optimal prefix code must already look like.

Setup. A binary prefix code corresponds to a binary tree with the symbols at the leaves and each codeword read off the root-to-leaf path. First: an optimal tree must be full — every internal node has exactly two children. If some internal node had only one child, deleting that node and attaching its child directly to the parent above shortens every codeword below it by one bit, strictly lowering E[l] — so an optimal tree could never contain such a node.

Lemma 1 (exchange argument: probability order matches length order). In an optimal code, p(x_i) > p(x_j) implies l(x_i) \leq l(x_j) — a strictly more probable symbol never sits at a strictly deeper leaf than a less probable one.

Suppose not: some optimal code has p(x_i) > p(x_j) but l(x_i) > l(x_j). Swap x_i and x_j's positions in the tree (exchange their codewords). The tree shape is unchanged, so the result is still a valid prefix code; only the expected length changes, by \Delta = \big(p(x_i)l(x_j) + p(x_j)l(x_i)\big) - \big(p(x_i)l(x_i) + p(x_j)l(x_j)\big) = \big(p(x_i)-p(x_j)\big)\big(l(x_j)-l(x_i)\big). The first factor is positive (p(x_i)>p(x_j)) and the second is negative (l(x_j)<l(x_i)), so \Delta < 0: the swap strictly lowers the expected length, contradicting optimality of the original code. So no such pair can exist in an optimal code.

A same-depth swap costs nothing by the identical computation: if l(x_i)=l(x_j), the second factor is 0 regardless of the probabilities, so \Delta=0 — relabeling two symbols at equal depth never changes E[l]. This fact is used below.

Lemma 2 (the two least-probable symbols can be siblings at maximum depth). Some optimal code has its two globally least-probable symbols as siblings (sharing a parent) at the tree's maximum depth.

Take any leaf at the tree's maximum depth d. Its sibling cannot be an internal node: an internal node's own children would sit at depth d+1, exceeding the tree's maximum depth d — impossible. So the sibling of any deepest leaf is itself a leaf at depth d; deepest leaves always come in sibling pairs. By Lemma 1's contrapositive, every leaf at depth d (the strictly largest depth present, when k>2) holds a probability no larger than any leaf at a shallower depth — the deepest level holds symbols from among the least probable in the whole distribution. Relabeling within that depth-d level costs nothing by Lemma 1's equal-depth case above, so the two globally least-probable symbols can always be swapped into one specific sibling pair at depth d without changing E[l].

Induction. k=1 is trivial (l=0, nothing to encode); k=2 is trivial (one bit each, and no shorter prefix code for two symbols exists). For k>2, assume the algorithm is optimal for every alphabet of size k-1. Let x,y be the two least-probable symbols of a k-symbol source. By Lemma 2, some optimal k-symbol code has x,y as siblings at maximum depth; merging them into one pseudo-symbol z with p(z)=p(x)+p(y) (deleting the shared parent's two leaves and relabeling that parent z) gives a valid (k-1)-symbol tree whose expected length is exactly E[l_k] - p(z) — each of x and y contributed one extra level of depth compared to z sitting at their parent's position, so removing that level removes exactly p(x)\cdot 1 + p(y)\cdot 1 = p(z) from the total. By the inductive hypothesis, the Huffman algorithm produces an optimal (k-1)-symbol tree for the distribution with z replacing x,y — and reattaching x,y as z's two children (exactly the algorithm's own next step, run in reverse) adds back precisely p(z) to any (k-1)-tree's expected length, optimal or not, by the identical accounting. Since the (k-1)-tree the algorithm builds is optimal among (k-1)-symbol trees, and the +p(z) adjustment applies uniformly, the reattached k-symbol tree is optimal among k-symbol trees too. The algorithm's first move — merge the two least-probable symbols — is exactly the move this argument requires, so induction carries the optimality claim through every step it takes.