Probabilistic Proof of Kraft-Mcmillan Inequality Let $\mathcal{C}$ be a finite binary code such that for any two sequences $\{a_n\},\{b_n\}\in \mathcal{C}$ if $a_j\not=b_j$ for some $j$ then the concatenation binary sequence $a_1a_2\cdots a_n\not=b_1b_2\cdots b_n$, the Kraft-Mcmillan Inequality says that
$$\sum_{i}\frac{N_i}{2^{i}}\le 1,$$where $N_i$ is the number of codes in $\mathcal{C}$ with length of $i$.
If we assume the code is prefix free, we will have an elegant probabilistic proof at here (consider the infinite binary sequence generated by i.i.d. binomial random variable with probability $1/2$, define $E_x$ be the event that the sequence has prefix $x\in \mathcal{C}$, then $\sum_i\frac{N_i}{2^i}\le \sum_i P[E_x]=  P[\cup_i E_x]=1$). But for the general case one will not necessarily have the events $E_i$s disjoint, I'm curious if similar argument exists for the general case. (The problem is an excercise in the probabilistic method of alon, I guess some probabilistic argument should exist)
(My attempt is that consider the product topology $T=\prod_i\mathcal C$ whose open sets generated by $E_x$s where $x$ is the concatenation codes of $\mathcal{C}$, we define a natural product measure $\mu$ over $T$ by $\mu(E_x)=2^{-|x|}$. Clearly $\mu(T)\le 1$ (as $T$ is a sub-topology of $\prod_i\{0,1\}$), I want to show $\mu(E_x\cap E_y)=0$ for $x\not=y\in \mathcal{C}$, if not we can find $E_z$ such that $E_z\subset E_x\cap E_y$ by compactness, if we can show $z$ can be write as concatenation code start with both $x,y$ we will done, but I get stuck at here.)
 A: EDIT: I originally posted a partial proof, and the OP showed me how to complete it in a comment.  I'm revising the post to give a complete proof.
Suppose on the contrary that $$\sum_{i=1}^{k}\frac{N_i}{2^{i}} > 1,$$ and let $E_n$ be the expected number of ways that a random binary string of length $n$ can be deciphered, where $n$ is longer than the longest codeword.  Then $$E_n = \sum_{i=1}^k\frac{N_i}{2^{i}}E_{n-i},$$
since the probability that the the first $i$ bits of the string is a codeword is $\frac{N_i}{2^{i}},$ and the expected number of ways to decipher the rest of the string is $E_{n-i}.$
If for some $n$ we have $E_n > 1,$ then there is some string of length $n$ with more than one decipherment, contradiction.
At this point, I was struggling with the roots of the characteristic equation, but the OP showed me a much simpler way.  The remainder of the proof is based on his insight.
Let $I = \{i| N_i > 0\}.$  Suppose $$n = \sum_{i \in I}{a_ii},$$ where the $a_i$ are nonnegative integers.  Then $E_n>0,$ because the string $$\sum_{i\in I}w_i^{a_i}$$ is a string of length $n$ with a decipherment.  Here each $w_i$ is a codeword of length $i,$ $w_i^{a_i}$ indicates the $a_i-$fold repetition of $w_i,$ and the sum means concatenation.  (Of course, the only way $E_n$ can be 0 is if no $n$-bit string has a decipherment.)
Now let $r = \text{gcd}(I).$  Then there is a $N$ such that for every $n\ge N, nr$ can be written in the form $$nr = \sum_{i \in I}{a_ii}, \text{ with }a_i\ge 0,$$ so that for sufficiently large $n, E_{nr} > 0.$  Then for some $n,$ in the recurrence $$E_{nr} = \sum_{i \in I}\frac{N_i}{2^{i}}E_{nr-i}\tag1, $$ every expectation on the right-hand side is positive.  Let $c$ be the minimum of these expectations. Then $$E_{nr} \ge c \sum_{i\in I}\frac{N_i}{2^{i}} = ct, \text{ where } t >1. $$
Now if we replace $n$ by $n+1$ in $(1)$, the minimum expectation on the right-hand side will be at least $c$, since $ct > c$. Thus, the same argument shows that $E_{nr+r} \ge tc.$  Continue in this manner through enough terms so that each expectation on the the right-hand side is $\ge tc.$  Then the next expectation in the sequence is $\ge t^2c,$ and we can find expectations $\ge t^hc$ for every positive integer $h$.  Since $t>1,$ some $E_n>1,$ which completes the proof.
The number-theoretic fact about representation of large multiples of $r$ follows at once from Schur's theorem, the $r=1$ case.  Schur gave his name to several theorems, so in googling it's better to search for "Frobenius coin problem."
