# Huffman Coding - probabilities

I am having trouble understanding a question related to Huffman Coding. We haven't studied it a lot, so I am not even sure how to start.

Given $n ≥ 2$ characters, with probabilities $p_{1} \geq p_{2} \geq ... \geq p_{n}$ Let $p_{i} = 2^{k_{i}}$ with $k_{i} \in \mathbb{N}$ and $\sum_{i=1}^{n} p_{i} = 1$

Show that $p_{n-1} = p_{n}$ and that the minimum expected codelength amount to $$- \sum_{i=1}^{n} p_{i} \log p_{i}$$

Help?

It's better to use the parametrization $p_i = 2^{-k_i}$. Multiply the equation $\sum_{i=1}^n p_i = 1$ by $2^{k_n}$ to get $$\sum_{i=1}^n 2^{k_n-k_i} = 2^{k_n}.$$ The right-hand side is even, so the number of $i$ such that $k_i = k_n$ must be even as well (why?). This implies that $p_{n-1} = p_n$.
For your second question, it is known that the minimum expected codeword length is at least $H(p) = \sum_i p_i \log (1/p_i) = \sum_i p_i k_i$. The converse to Kraft's inequality shows that there is a prefix code with codeword lengths $k_1,\ldots,k_n$, and so with expected codeword length $H(p)$.