Page 491, Exercise 1

The complete proofs on path length are quite involved.  They are discussed in depth in The Art of Computer Programming, Volume 1 by Donald Knuth (Section 2.3.4.5).