I am moving through a classic paper (On [Average Height of Planted Plane Trees](http://alexandria.tue.nl/repository/freearticles/597601.pdf) 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.)



An identity involving a sum of binomial coefficients
Terry Tao answered my question in a comment. See edit at the end of the main post.


