> [!theoremb] Theorem > > Given a [[Code|code]] alphabet of $r$ symbols, a prefix-free code with codewords of length $l_i$ exists for a source alphabet of $n$ symbols if and only if > $ > \sum_{i = 1}^{n}r^{-l_i} \le 1 > $ > > *Proof*. Suppose that the theorem holds. > > Let $L$ be the maximum codeword length, and let $n_i$ be the number of codewords of length $i$, then rewrite the theorem as: > $ > \sum_{i = 1}^L n_i r^{-i} \le 1 > $ > > Multiply both sides by $r^L$ to obtain: > $ > \sum_{i = 1}^L n_i r^{L-i} \le r^L > $ > Rearrange the sum, > $ > n_L \le \sum_{i = 1}^{L - 1}n_ir^{L - i} > $ > Since $n_L \ge 0$, the right hand side $\ge 0$, meaning that: > $ > \begin{align*} > n_{L - 1}r &\le \sum_{i = 1}^{L - 2}n_ir^{L - i} \\ > n_{L - 1} &\le \sum_{i = 1}^{L - 2}n_ir^{L - i - 1} > \end{align*} > $ > Since $n_{L - 1} \ge 0$, the argument can be applied again > $ > \begin{align*} > n_{L - 2}r &\le \sum_{i = 1}^{L - 3}n_ir^{L - i - 1} \\ > n_{L - 2} &\le \sum_{i = 1}^{L - 3}n_ir^{L - i - 2} > \end{align*} > $ > Such that, > $ > n_{L - k} \le \sum_{i = 1}^{L - k}n_ir^{L - i - k} > $ > By [[Axiom of Induction|induction]], this statement is true for all $0 \le k \le L - 1$. > > To construct the code, start with words of length 1. Since there are $n_1$ words of length 1, and $n_1 \le r$, we have complete freedom in choosing them. > > Moving onto words of length 2, there are $r - n_1$ possible starting letters, and therefore $(r - n_1)r$ possible codewords. As $n_2 \le r^2 - n_1r$, we have freedom in choosing them. > > Moving onto words of length 3, there are $r^2 - n_1r - n_2$ possible starting combinations, and therefore $(r^2 - n_1 r - n_2)r$ possible codewords. > > By induction, a system of pre-fix free codewords may be constructed. Going in reverse, any pre-fix free code must follow the theorem.