<p>I am moving through a classic paper (On <a href="http://alexandria.tue.nl/repository/freearticles/597601.pdf">Average Height of Planted Plane Trees</a> 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}$.</p>

<p>The outline from the article is as follows and may be skipped.</p>

<blockquote>
<p>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].
$$</p>
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.)
</blockquote>

<p>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?</p>