# Proof for an identity involving a sum of binomial coefficients

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?

• 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. Dec 24, 2012 at 5:48
• My apologies. I won't do it again. Thank you for the link. Dec 24, 2012 at 10:50