Theorem D

For all ,

 

where

 

Here is the entropy function and .

Proof D

Let , where

and

Then C has the property that for any binary word of length k there is a unique with a prefix of . Now for any with length

where the sum is over all of length k for which is a prefix of . Hence

From (2.16) this implies that

where denotes the number of vectors in . The already proved first part of Theorem A shows that

so that to prove (2.17) it suffices to bound from above.

Now the definition (2.15) of an inflating vector implies that

so that

 

The right side of (2.19) is just the tail of the binomial distribution. It is easily checked using Stirling's formula that for any constant and any the bound

holds for all sufficiently large k. With more work one can obtain the more precise estimate (Ash [8], Lemma 4.7.2) that for any

which used in (2.19) implies (2.17).