Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.
Рассмотрим любой однозначный код с <tex>k</tex> кодовыми словами <tex>P_1, ..., P_k</tex>. Для удобства при кодировании вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> соответственно.
Представим сумму всех слов (кодируемых через <tex>a</tex> и <tex>b</tex>) и возведем эту сумму в степень <tex>N</tex> (любое натуральное число): <tex>(P_1+P_2+...P_k)^N</tex>. Раскрывая Раскроем скобки, сохраним порядок переменных и не будем собирать их вместе (то есть возводить их в степень)подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.
Вот пример для однозначного кода со словами <tex>a,ab,bb</tex> и <tex>N=2</tex>:
<tex>(a+ab+bb)^2</tex><tex>=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.</tex> Все получившиеся слагаемые (слова) различны (соответствует определению однозначности).
Если неравенство верно для букв, то оно верно для любых числовых значений. Подставим <tex>a=b=\frac{1}{2}</tex> в неравенстводля того, чтобы получить <tex>{\frac{1}{2}}^{n_i}=2^{-n_i}</tex>, где <tex>{n_i}</tex> длина кодового слова. В левой части получится выражение из неравенства Макмиллана: <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_k})^N</tex>. Всего имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex> равных <tex>2^{-l}</tex>, следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N \le N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.
}}
