= Solution
The binary <Kraft inequality> says that codeword lengths $l_1,l_2,\ldots$ of a <prefix code> satisfy
$$
\sum_i2^{-l_i}\leq1.
$$
Conversely, suppose positive integer lengths obey this inequality and arrange them in nondecreasing order. Construct codewords greedily in the infinite binary tree. Before assigning length $l_i$, each earlier codeword of length $l_j\leq l_i$ excludes exactly $2^{l_i-l_j}$ nodes at depth $l_i$. Thus the number excluded is
$$
\sum_{j<i}2^{l_i-l_j}
=2^{l_i}\sum_{j<i}2^{-l_j}
<2^{l_i},
$$
where strictness follows because the remaining term $2^{-l_i}$ occurs in the full Kraft sum. A free depth-$l_i$ node therefore exists. Assign it as the next codeword; choosing a node not below an earlier codeword preserves prefix-freeness. Induction constructs the required prefix code.
Back to article page
