help proving an binomial identity about catalan numbers 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$. 
 A: 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]$.
