I'm studying probabilistic methods at the moment and i saw this problem which i can not provide a probabilistic proof for it. I would be really thankful if someone could provide me with that.
Let $F$ be a finite collection of binary strings of finite lengths, and assume that no member of $F$ is a prefix of another one. Let $N_i$ denote the number of string of length $i$ in $F$. Prove that $$\sum_{i=0}^n \frac{N_i}{2^i} \leq 1$$
Generate a long string $S$ (of size, say, $N=\sum_{i \in I}I$, where $I$ is a subset of positive integers, for which for every $i \in I$, there is a binary string of length $i $ in $F$), where each bit is $0$ or $1$, uniformly at random.
Now, let $E_i$ to denote the event that the first $i $ bits of $S$ coincides with one of $i $-bit codewords in $F$. It is clear that, $\mathbb{P}(E_i)=N_i/2^i $. Furthermore, since the strings are prefix free, it follows that $\{E_i\}_{i \in I}$ is a collection of disjoint events. Now, $$ 1\geq \mathbb{P}(\bigcup_{i \in I}E_i)=\sum_{i \in I}\mathbb{P}(E_i)=\sum_{i \in I}\frac{N_i}{2^i}, $$ where the first equality is due to disjointness. We are done.