Kraft-McMillan inequality Let $F$ be a finite collection of binary string of finite lengths and assume that no two distinct concatenations of two finite sequences of codewords result in the same binary sequence. Let $N_i$ denote the number of string of length $i$ in $F$. Prove 
$$\sum_i \frac{N_i}{2^i}\leq 1$$
[Source: The probabilistic method, Alon and Spencer]
There is a question that clarifies the statement of the problem, but doesn't mention anything about how to solve the problem itself. 
 A: Suppose that the strings come from a non-binary alphabet source $\chi$, hence we can encode each symbol as $C(x)$, which is a binary sequence and $C$, is our encoder. we represent the length of $C(x)$ by $|C(x)|$. Hence we have for any $m>0$:
$(\sum_{x\in \chi}2^{-|C(x)|})^m=\sum_{u_1\in \chi}\sum_{u_2\in \chi}...\sum_{u_m\in \chi}2^{-|C(u_1)|}2^{-|C(u_2)|}...2^{-|C(u_m)|}=\sum_{u_1\in \chi}\sum_{u_2\in \chi}...\sum_{u_m\in \chi}2^{-|C(u_1)C(u_2)...C(u_m)|}$
Let $N_{max}=\max{(|C(x)|:x\in \chi)}$
then for any sequence $u_1u_2...u_m$ we have $|C(u_1)C(u_2)...C(u_m)|\leq mN_{max}$ in which $C(u_1)C(u_2)...C(u_m)$ is the concatenation of the binary sequences regarding to $u_1,u_2,...u_m$ respectively. 
For any $1\leq i\leq mN_{max}$, let the $N_i$ be the number of sequences $u_1u_2...u_m$ such that $|C(u_1)C(u_2)...C(u_m)|=i$, then:
$(\sum_{x\in \chi}2^{-|C(x)|})^m=\sum_{i=1}^{mN_{max}}N_i2^{-i}$.
It is completely evident that $N_i\leq 2^i$, thus
$(\sum_{x\in \chi}2^{-|C(x)|})^m=\sum_{i=1}^{mN_{max}}N_i2^{-i}\leq \sum_{i=1}^{mN_{max}}2^i2^{-i}=mN_{max}$
Hence $\sum_{x\in \chi}2^{-|C(x)|}\leq \sqrt[m]{mN_{max}}$
Now let $m\rightarrow \infty$, then we have:
$\sum_{x\in \chi}2^{-|C(x)|}\leq1$
This theorem is an important theorem in digital communication. Indeed when we want to examine a mapping from a non-binary alphabet to a binary sequence, is uniquely decodable, then one of the important touchstones is Kraft inequality 
