Solution
= Solution
The Shannon lengths are $l_S(a)=\lceil\log_2(1/P(a))\rceil$. Their <Competitive optimality of the Shannon code> says that for every binary uniquely decodable code of lengths $l_C$ and every positive integer $k$,
$$
\mathbb P\{l_S(X)\geq l_C(X)+k\}\leq2^{-k+1}.
$$
On this event, $P(X)<2^{-l_C(X)-k+1}$. Summing and applying the <Kraft inequality> proves
$$
\mathbb P\{l_S(X)\geq l_C(X)+k\}
\leq2^{-k+1}\sum_a2^{-l_C(a)}\leq2^{-k+1}.
$$