Доказательство. Пусть для какого-нибудь

Пусть для какого-нибудь . Тогда по предыдущему свойству , но по условию , отсюда . Построим код , переставив два кодовых слова в коде , то есть положим .

Рассмотрим

, – оптимальный код. Переставив так все кодовые слова, для которых , получим код , и длины кодовых слов будут расположены по неубыванию, длина . Но возможно, кодовые слова максимальной длины, отличающиеся только в последнем разряде не будут стоять рядом. Пусть но тогда длина также равна . Переставив местами кодовые слова и , получим код , рассмотрим =

, цена кодирования не изменилась, – оптимальный код.