# An identity involving a sum of binomial coefficients

I am moving through a classic paper (On 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$. (They go about it with an integral on the complex plane.)

If I am not mistaken, this boils down to prove $$\sum_{k \geqslant 1}\sum_{h \geqslant 1}\binom{2n}{n+a-kh} = \sum_{k' \geqslant 1}d(k') \cdot \binom{2n}{n+a-k'}.$$ How would you approach this identity without using complex analysis?

EDIT: Terry Tao nailed it in a comment below: if we write all the binomial coefficients summed in the left-hand side, we can regroup them by multiples of $k$, that is, by divisors of $k'$. (What obscures this simple argument is to use $k$ on the right-hand side as well and think that it is the same as in the left-hand side.)

• Crossposted to math.SE: math.stackexchange.com/q/264137/264 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. – Zev Chonoles Dec 24 '12 at 5:47
• I think all that the authors are doing here is expanding $d(k) = \sum_{k = k' h} 1$, then interchanging summations, then relabeling $k'$ as $k$ (and also shifting $h$ by $1$). – Terry Tao Dec 24 '12 at 8:07

It isn't true. Choose $n,a,k$ such that $n+a-k>0$, $n+a-2k<0$ and $k>1$. The sum has only one nonzero term which is not equal to the right side.