help proving an binomial identity about catalan numbers

Question

I need help proving the following identity:

$$\sum_{k=0}^n \frac{1}{k+1} \binom{2k}{k} \binom{2n-2k}{n-k} = \binom{2n+1}{n}.$$

It has to do with the Catalan numbers and Dyck walks. Notice that $$\frac{1}{k+1} \binom{2k}{k}$$ is the Catalan number $C_k$.

Answer 1

Here is an answer based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k}}\\ &=\sum_{k=0}^\infty[z^k]\frac{2}{1+\sqrt{1-4z}}[t^{n-k}](1+t)^{2n-2k}\tag{1}\\ &=[t^n](1+t)^{2n}\sum_{k=0}^\infty\left(\frac{t}{(1+t)^2}\right)^k[z^k]\frac{2}{1+\sqrt{1-4z}}\tag{2}\\ &=[t^n](1+t)^{2n}\cdot\frac{2}{1+\sqrt{1-\frac{4t}{(1+t)^2}}}\tag{3}\\ &=[t^n](1+t)^{2n+1}\tag{4}\\ &\color{blue}{=\binom{2n+1}{n}}\tag{5} \end{align*}

Comment:

• In (1) we apply the coefficient of operator twice. Here we use the generating function $\frac{2}{1+\sqrt{1-4z}}$ of the Catalan numbers. We also set the limit to $\infty$ without changing anything since we are adding zeros only.

• In (2) we use the linearity of the coefficient of operator and apply the rule $$ [t^{p-q}]A(t)=[t^p]t^qA(t) $$ We also do some rearrangements as preparation for the next step.

• In (3) we apply the substitution rule of the coefficient of operator with $z:=\frac{t}{(1+t)^2}$
  \begin{align*} A(t)=\sum_{k=0}^\infty a_k t^k=\sum_{k=0}^\infty t^k [z^k]A(z) \end{align*}

• In (4) we do some simplifications.

• In (5) we select the coefficient of $[t^n]$.