Solution
= Solution
For a $q$-ary code with codeword lengths $l_1,\ldots,l_m$, <Kraft inequality> is
$$
\boxed{\sum_{i=1}^m q^{-l_i}\leq1}.
$$
Choose an infinite random $q$-ary string with independent uniform symbols. The event that it begins with codeword $i$ has probability $q^{-l_i}$. For a <prefix code>[prefix-free code], these events are disjoint, so their probabilities sum to at most one. This proves necessity.