For all,
![]()
where
![]()
Here
is the entropy function and
.
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).