[22] We derive a lower bound on the minimal average codeword length of prefix-codes. Consider the standard correspondence between binary strings and integers as in Equation 1.3. Define f(n) =

l(n) + l(l(n)) + ··· + 2. Show that 

n 2−f(n) = ∞.

Comments. Hint: Let the number of terms in f(n), apart from the 2, be h(n) = 0 for n = 2 and 1 + h(h(n)) for n > 2 (this defines function h).

Define si = 

h(n)=i 2−f(n) and ∞

n=3 2−f(n) = ∞

i=0 si. We show that all si are equal to 1, using induction on i. Clearly s0 = 2−0 = 1. Also si+1 =

h(n)=i+1 2−f(n) =

h(l(n))=i 2−f(n)

=

h(m)=i l(n)=m 2−(m+f(m)) =

h(m)=i 2m2−(m+f(m)) = si.