<s>[INST] Combinatorics Identity about Catalan numbers: $\sum_{k=0}^n \frac{1}{k+1}\binom{2k}k \binom{2n-2k}{n-k}=\binom{2n+1}n$ I need to prove this identity:
$\sum_{k=0}^n \frac{1}{k+1}{2k \choose k}{2n-2k \choose n-k}={2n+1 \choose n}$
without using the identity:
$C_{n+1}=\sum_{k=0}^n C_kC_{n-k}$.
Can't figure out how to.
 [/INST] Suppose we seek to prove that
$$\sum_{k=0}^n \frac{1}{k+1} {2k\choose k}
{2n-2k\choose n-k} = {2n+1\choose n}.$$
We get for the LHS
$$[z^n] (1+z)^{2n} \sum_{k=0}^n \frac{1}{k+1} {2k\choose k}
\frac{z^k}{(1+z)^{2k}}.$$
Here the coefficient extractor $[z^n]$ combined with the factor $z^k$
enforces the upper limit of the sum which we may thus extend to
infinity:
$$[z^n] (1+z)^{2n} \sum_{k\ge 0} \frac{1}{k+1} {2k\choose k}
\frac{z^k}{(1+z)^{2k}}.$$
Now the generating function of the Catalan numbers is
$$\frac{1-\sqrt{1-4z}}{2z}$$ so this simplifies to
$$\begin{align*}
& [z^n] (1+z)^{2n} \frac{1-\sqrt{1-4z/(1+z)^2}}{2z/(1+z)^2}
\\ = & [z^{n}] (1+z)^{2n+1}
\frac{1+z-\sqrt{(1+z)^2-4z}}{2z}
\\ = & [z^{n}] (1+z)^{2n+1}
\frac{1+z-\sqrt{(1-z)^2}}{2z}
\\ = & [z^n] (1+z)^{2n+1}
= {2n+1\choose n}
\end{align*}$$
as claimed.
</s>