I am moving through a On The Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my skills are not up for the task. I would simply like to prove that the average height $h_n$ of a tree with $n$ nodes (i.e. the maximum number of nodes from the root to a leaf) satisfies $h_n \sim \sqrt{\pi n}$.

The outline from the article is as follows and may be skipped.

Let $A_{nh}$ be the number of trees with height less than or equal to $h$ (with the convention $A_{nh} = A_{nn}$ for all $h \geqslant n$) and $B_{nh}$ the number of trees of $n$ nodes with height greater than or equal to $h+1$ (that is, $B_{nh} = A_{nn} - A_{nh}$). Then $h_n = S_n/A_{nn}$, where $S_n$ is the finite sum $$ S_n = \sum_{h \geqslant 1} h(A_{nh} - A_{n,h-1}) = \sum_{h \geqslant 1} h(B_{n,h-1} - B_{nh}) = \sum_{h \geqslant 0} B_{nh}. $$ It is well known that $A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$, for the set of general trees with $n$ nodes is in bijection with the set of binary trees with $n-1$ nodes, counted by the Catalan numbers. Thus, the first step is to find $B_{nh}$ and then the main term in the asymptotic expansion of $S_n$. At this point the authors use analytical combinatorics (three pages) to derive $$ B_{n+1,h-1} = \sum_{k \geqslant 1} \left[\binom{2n}{n+1-kh} - 2\binom{2n}{n-kh} + \binom{2n}{n-1-kh}\right]. $$

Then they say that $$ S_{n+1} = \sum_{k \geqslant 1}d(k) \cdot \left[\binom{2n}{n+1-k} - 2\binom{2n}{n-k} + \binom{2n}{n-1-k}\right], $$ where $d(k)$ is the number of positive divisors of $k$.

If I am not mistaken, this boils down to prove \begin{gather*} \sum_{h \geqslant 0}\left[\binom{2n}{(n-k)+1-kh} - 2\binom{2n}{(n-k)-kh} + \binom{2n}{(n-k)-1-kh}\right] =\\ d(k) \cdot \left[\binom{2n}{n+1-k} - 2\binom{2n}{n - k} + \binom{2n}{n-1-k}\right]. \end{gather*} How would you approach this identity without using complex analysis?

  • 2
    $\begingroup$ Crossposted to MathOverflow. In the future, please wait some time before posting your question in multiple fora, and when you do, provide links to the other posts - as you can imagine, it would be frustrating for someone to put time into answering your question here, only to see hear from you that you'd already gotten the solution elsewhere. $\endgroup$ Dec 24, 2012 at 5:48
  • 1
    $\begingroup$ My apologies. I won't do it again. Thank you for the link. $\endgroup$ Dec 24, 2012 at 10:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.