Let $C_n=\frac1{n+1}\binom{2n}n$ be the $n^\text{th}$ Catalan number. I discovered the below identity through some generating function magic, and was wondering if anyone could come up with a combinatorial interpretation and proof.

For $n\ge 0$, $$ 2n C_n=\sum_{k=1}^n\binom{2k}kC_{n-k}. $$

I have been trying to interpret the right as a walk of length $2k$ on the integer line which return to where it starts, followed by a walk of length $2(n-k)$ which does not dip below the $x$ axis. Such a walk is labeled at $2k$. Also, $C_n$ counts walks, and $n$ could tell you where to place the label, and then somehow transform to path to get in the form described before. But I cannot quite get the mapping to work out.

If you are curious as to where this came from, you can show that letting $C(x)=\sum_{n\ge 0}C_n x^n$, and letting $F(x) = \sum_{n\ge 1} \frac{1}{2n}\binom{2n}nx^n$, that $C(x) = e^{F(x)}$. Differentiating, this implies $xC'(x) = xF'(x)C(x)$, and the claim follows.

  • 1
    $\begingroup$ You might be able to get something out of writing the right hand side as $$\sum (k + 1) C_k C_{n-k}. $$ $\endgroup$ – Trevor Gunn Aug 25 '18 at 19:14

Here is a combinatorial proof that $$ \binom{2n}{n} - C_n = \sum_{k=1}^n \frac12\binom{2k}{k} C_{n-k}. $$ Since $C_n = \frac{1}{n+1}\binom{2n}{n}$, the left-hand side simplifies to $n C_n$, and after multiplying by $2$, this gives us the equation you want.

Both sides of the equation above are going to count walks of length $2n$ that start and end at $0$, but do dip below the $x$-axis. Since $\binom{2n}{n}$ counts the total number of walks that start and end at $0$, and $C_n$ counts the number that don't dip below the $x$-axis, the number we are counting is $\binom{2n}{n} - C_n$.

Now split these walks up into $n$ classes based on the last step at which the walk goes from $-1$ to $0$. Such a step must exist, because once we dip below the $x$-axis, we have to come back up to $0$ at some point.

The number of walks in which this step is the $(2k)^{\text{th}}$ step is exactly $\frac12 \binom{2k}{k} C_{n-k}$:

  • Out of the $\binom{2k}{k}$ walks that return to $0$ on the $(2k)^{\text{th}}$ step, exactly half go from $-1$ to $0$ on that step. (The other half go from $1$ to $0$.)
  • In the remainder of the walk, we can never dip below $0$, since that step was the last time we came back from below the $x$-axis, so there are $C_{n-k}$ ways to complete the walk.

Summing over all values of $k$, we get the right-hand side of the equation above.

  • $\begingroup$ Love it, thank you! $\endgroup$ – Mike Earnest Aug 26 '18 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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