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.)
