Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 1 / 4H / Solution

A binary uniquely decodable code assigns a finite binary word to each source symbol, so that no two distinct finite sequences of source symbols have the same concatenated encoding. This does not require the stronger prefix property. All codeword lengths are positive.

Put $S={\sum }_j{2}^{-l_j}$ and let $A_{k,L}$ count sequences of $k$ source symbols whose encoded total length is $L$. Expanding the product givesUnique decodability makes these encodings distinct, so $A_{k,L}\le 2^L$, the number of binary strings of that length. There are at most $k(l_{\max }-l_{\min })+1$ possible lengths. ThereforeTaking $k$th roots and letting $k\to \infty$ proves the McMillan inequality: