# Combinatorial proof of Catalan number/central binomial convolution: $2n C_n=\sum_{k=1}^n\binom{2k}kC_{n-k}$

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.

• You might be able to get something out of writing the right hand side as $$\sum (k + 1) C_k C_{n-k}.$$ – 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.

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