I'm working on exercise 16.3-5 of CLRS:
Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword lengths are monotonically increasing.
Perhaps I'm misunderstanding the question, but how can the lengths be monotonically increasing? In order for the code to be optimal, the binary tree representation must be full (like the StackExchange CS logo), e.g. every node with degree either 0 or 2 (if it's not full, then it cannot be optimal, since the code could be shortened by promoting the child of a node with degree 1, as discussed in exercise 16.3-2). That means there exists at least one pair of leaf nodes at the same depth, and depth is the same thing as the codeword length.
The Huffman code is optimal, and it always begins by merging two characters, so again there's at least a single pair of leaf nodes that will be at the same depth and hence same codeword length in the resulting tree.
Is it a typo, e.g. should it read "monotonically increasing except for the final two characters, which have the same length" or maybe even "monotonically non-decreasing"?
In fact, there is a trivial counterexample: suppose there are only two characters 'a' and 'b', with frequencies 0.6 and 0.4 respectively. The optimal code is clearly 'a'=0 and 'b'=1, or vice versa. However, the codelength is 1 for both characters, so clearly is not monotonically increasing.
