Encoding
霍夫曼編碼是前綴碼，證明
$$ \forall x,y \in C,\ \forall z \in \lbrace 0,1\rbrace^*,\ x\not=y||z $$ 使用歸納根據項目數編碼？基本步驟很容易，但我不知道如何證明歸納步驟。
讓 $ T $ 是最優前綴碼樹，令 $ b $ 和 $ c $ 是樹的最大深度的兩個兄弟姐妹（必須存在，因為 $ T $ 已滿）。不失一般性假設 $ f (b) \le f(c) $ 和 $ f(x) \le f(y) $ （如果這不是真的，那麼重命名這些字元）。自從 $ x $ 和 $ y $ 有兩個最小的頻率，它遵循 $ f(x) \le f(b) $ （它們可能相等）和 $ f(y) \le f(c) $ （可能相等）。因為 $ b $ 和 $ c $ 位於我們知道的樹的最深處 $ d(b) \ge d(x) $ 和 $ d(c) \ge d(y) $ . 現在換個位置 $ x $ 和 $ b $ 在樹中導致不同的樹 $ T′ $ 看看成本如何變化。自從 $ T $ 是最優的，
$$ \begin{align} B(T) &\le B(T′) \ &= B(T) − f(x)d(x) − f(b)d(b) + f(x)d(b) + f(b)d(x) \ &= B(T) − (f(b) − f(x))(d(b) − d(x)) \ &\le B(T) \end{align} $$ 所以， $ B(T′) = B(T) $ ， 那是， $ T′ $ 是一棵最優樹。通過切換 $ y $ 和 $ c $ 我們得到一棵新樹 $ T ′′ $ 通過類似的論點，這是最佳的。最後的樹 $ T′′ $ 滿足索賠的陳述。