Date: Wed, 08 Jan 1997 20:46:43 GMT Server: NCSA/1.4.2 Content-type: text/html
We can prove this by induction on n:
Basis: The statement is true for n = 1 because
.
Inductive hypothesis: Assume that the statement is true for n=k:
Inductive step: From this we need to show it is true for n=k+1:
By induction, the statement is true for all .
This is because if we look at the strings of length 2n, the first strings
in the enumeration are those that begin with .
Of the strings that begin with
,
is the first
and
is the last of these. This gives us the following:
The rank of is
.
The number of strings of length 2n that begin with
is just
the number of ways of writing the last n letters as a string in the alphabet.
There are
such ending strings. Combining these observations gives us:
In the enumeration ordering, the strings that come before are exactly
the strings over
whose length is less than n. Therefore,
For any i, the number of strings of length i is .
Thus the number of strings of length less than n is the sum of all these,
so: