A question regarding a prefix code Let $C=\{ c_1, c_2, \dots, c_m \}$ be a set of sequences over an alphabet $\Sigma$ and $|\Sigma|=\sigma$. Assume that $C$ is a prefix-free code, in the sense that no codeword in $C$ is a prefix of another codeword in $C$, with $|c_i|= n_i\ \forall i$. Prove that $\sum_{h=1}^m \sigma^{-n_h} \leq 1$.
My attempt:
I want to argue that $C$ is a finite subset of all the keywords that can be built and therefore we have the following:
$p(creating\ c_i)= \frac{1}{\sigma^{n_i}},$
$\sum_{h=1}^m \sigma^{-n_h}= \sum_{i=1}^m p(creating\ c_i)\leq \sum_{i=1}^\infty p(creating\ c_i) = 1$
Would you please help me figure out if I am doing it right?
Thanks
 A: We know that a prefix free code can be represented as a tree. At each node of the tree there are at most $\sigma$ branches.
Now I prove the theorem by induction on depth of the tree.
Base case:
depth of tree is 1, so we know for a fact that there are at most $\sigma$ of length one branches. So easily we can see that the sum is at most
$\sum_1^m \sigma^{-1} \le 1$.
Induction:
Now assume that for any tree of depth $h$ we know that the inequality holds and we want to prove it for $h+1$. Now consider a tree of depth $h+1$, we can break it down from the root. So any subtree starting from a node under the root is a tree of the depth $h$ and the equation holds for them.
So for any subtree $t_j$ I can write:
$\sum_{c_i \in t_j} \sigma^{-h} \le 1$.
Okay, now consider the original tree, knowing that each code is a part of some subtree I can break down it to the subtrees formula:
$\sum_{c_i} \sigma^{-(h+1)} = \sum_j \sum_{c_i \in t_j} \sigma^{-(h+1)} = \sum_j \sigma^{-1} \sum_{c_i \in t_j} \sigma^{-(h)}$
Now using the induction assumption:
$\sum_j \sigma^{-1} \sum_{c_i \in t_j} \sigma^{-(h)} \le \sum_j \sigma^{-1} \le 1$
the last one is due to the fact that there are at most $\sigma$ subtrees.
A: @mnz has given a prefectly rigorous answer. There is another proof that works for any uniquely decodable scheme, i.e. given a sequence of letters from the alphabet, there is at most one way to separate the letters such that each subsequence is in $C$. It's clear that prefix-free codes can be uniquely decoded.
We define the "weight" of a sequence of letters to be $\sigma^{-l}$ where $l$ is the length of the sequence. Then the total weight of all the sequences of $l$ messages (not letters!) is just (where the first sum is taken over all sequences  $(x_1, \cdots, x_l)$ of numbers from $1$ to $m$) $$\sum_{(x_1, \cdots, x_l)} \sigma^{-(n_{x_1}+n_{x_2}+\cdots+n_{x_l})} = (\sum_{h=1}^m \sigma^{-n_h})^n$$
On the another hand, the total weight of all sequences of length at most $l\cdot(\max_h n_h)$ is simply $l\cdot(\max_h n_h)$: There are exactly $\sigma^{l'}$ sequences of length $l'$ and each of them has weight $\sigma^{-l'}$, hence the total weight of sequences for a fixed length $l'$ is just $1$, and $l'$ can take at most $l\cdot(\max_h n_h)$ values.
Since each sequence can be decoded uniquely, there must be $$(\sum_{h=1}^m \sigma^{-n_h})^n\le l\cdot(\max_h n_h)$$
Note that while the RHS grows linearly, the LHS cannot grow exponentially, therefore $\sum_{h=1}^m \sigma^{-n_h}\le 1$.
