Shannon's noiseless source coding theorem

For the lower bound, let $l_i$ be the lengths of any prefix code, so $\sum_{i=1}^n 2^{-l_i} \le 1$. Define $q_i = 2^{-l_i}/Z$ where $Z=\sum_j 2^{-l_j} \le 1$, so $q$ is a probability distribution. By Gibbs' inequality, $0 \le D(p\|q) = \sum_i p_i \log_2(p_i/q_i) = \sum_i p_i\log_2 p_i - \sum_i p_i \log_2(2^{-l_i}/Z) = -H(X) + \sum_i p_i l_i + \log_2 Z$. Since $Z \le 1$, $\log_2 Z \le 0$, so $0 \le -H(X) + L + \log_2 Z \le -H(X) + L$, which rearranges to $L \ge H(X)$.

For the upper bound (achievability), choose $l_i = \lceil -\log_2 p_i \rceil$ for each $i$ (round the ideal length up to the nearest integer). These lengths satisfy Kraft's inequality since $2^{-l_i} \le 2^{-(-\log_2 p_i)} = p_i$, so $\sum_i 2^{-l_i} \le \sum_i p_i = 1$; by the Kraft–McMillan construction such lengths can always be realized as an actual prefix code (build the code by assigning binary strings level by level in a binary tree).

By definition of ceiling, $l_i < -\log_2 p_i + 1$. Multiplying by $p_i \ge 0$ and summing over $i$ gives $L = \sum_i p_i l_i < \sum_i p_i(-\log_2 p_i + 1) = H(X) + 1$.

Combining both parts, this construction achieves $H(X) \le L < H(X) + 1$.