MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Crossposted to math.SE: 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.

share|cite|improve this answer
Thanks. That was too strong a condition. I restated above. – Christian Dec 25 '12 at 12:56
up vote 0 down vote accepted

Terry Tao answered my question in a comment. See edit at the end of the main post.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.