I was given a task of proving some inequalities that are related to Kraft-McMillan's inequalities, and i have been scratching my head for quite some time trying to prove it:
$$ F(x)= \frac{1}{1-Q(x) } $$
where $F(x)$ is: $$ F(X)=1+N(1)x+N(2)x^2+... $$ and $$ Q(x)=\sum_{r=1}^l n_rx^r $$
reading the definition in the proof section of the article will make things clearer: Link to essay
EDIT:
some definitions: Given a Separable list B l- length of the max separable word. $ n_r $ - number of words which are of length r where $ 1\lt= r \lt= l $
a list will be called separable if, whenever a string of words of B will be written written out in letters, without space marks between the words, the resulting string is uniquely decipherable into the original string of words. example: "together" and "to get her" is an example of not a separable string of words.
Let $N(k)$ be the number of distinct sequences of words of B each of which, written as a string of letters, is of total length of k.
thanks in advance
Suppose we index the words in our list as $B = \{ w_1, w_2, ..., w_n \}$.
How can we form a string of $t$ words from the list? Well, we choose some first word $w_{i_1}$, a second word $w_{i_2}$, and so on, until we have a $k$th word $w_{i_t}$, and then we stick them all together: $w_{i_1} w_{i_2} ... w_{i_t}$.
If we think of concatenation as multiplication of words, and addition as listing all possible choices, then we can represent the collection of all strings of $t$ words as $\sum_{i_1, i_2, ..., i_t \in [n]} \prod_{j=1}^t w_{i_j}$, which factors to give $( \sum_{i =1}^n w_i )^t$.
However, this gives us the number of words in the string, whereas we are interested in the total length of the string instead. To get this algebraically, we will have to replace the words $w_i$ with something that keeps track of how long the word is.
The neat way to do this is to imagine we take the word, and replace each letter in the word with the variable $x$. Then any word of length $r$ becomes the monomial $x^r$. The nice thing about this substitution is that concatenation truly becomes multiplication: the concatenation of a word of length $r$ with a word of length $s$ is a string of length $r+s$, while $x^r \times x^s = x^{r+s}$.
So what happens to our word equation? Well, first consider each factor $\sum_{i=1}^n w_i$. Every word $w_i$ gets replaced by $x^{r_i}$, where $r_i$ is the length of the word $w_i$. Grouping together like terms, we find that $\sum_{i=1}^n w_i \mapsto \sum_{r=1}^{\ell} n_r x^r$, since there are exactly $n_r$ words of length $r$. This gives us the quantity $Q(x)$.
Hence we have shown that $Q(x)^t$ is what we would get if we take all strings of $t$ words from the list and replace every letter with the variable $x$. Again, if we were to group together the like terms, we would have $Q(x)^t = \sum_{r=1}^{\infty} N_t(r) x^r$, where $N_t(r)$ is the number of strings of $t$ words with total length equal to $r$.
This is almost what we want, but we don't want to restrict the number of words that the string is made out of - we don't care about $t$. Hence we will sum these equations up for all values of $t$. Algebraically, it is nice to include the case $t = 0$. This corresponds to the empty string, which has length $0$, and hence gets replaced by $x^0 = 1$. All other terms will involve actual words, and thus have positive degree. We thus find $F(x) = \sum_{t = 0}^{\infty} Q(x)^t = \sum_{r=0}^{\infty} N(r) x^r = 1 + N(1) x + N(2) x^2 + ...$, where $N(r)$ is now the total number of strings of (any number of) words of total length $r$.
Finally, we observe that we have a geometric series with common ratio $Q(x)$, so $F(x) = \sum_{t=0}^{\infty} Q(x)^t = \frac{1}{1 - Q(x)}$. You may be a little concerned that here we are dealing with abstract power series, and not real numbers, but this can be shown to be valid in the realm of power series (since in $(1 - Q(x))(\sum_{t = 0}^{\infty} Q(x)^t)$, all but the constant term $1$ cancel out (very formally, one would define convergence and take a limit, but I won't do that here)).
I hope that helps!