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.

Solution 1:

Let's try to solve the following problem : Given a grid of $(n+1)*n$, count the number of ways to move from the lower left corner to the upper right corner while moving only right or up in one step.

One way to do this is straightforward. You have total $2n + 1$ moves, out of which $n$ moves should be up moves and the rest should be right moves. The number of sequence of length $2n+1$ with $n$ up moves and $n+1$ right moves is $\binom{2n+1}{n}$.

Another way to do this is as follows : Consider a diagonal of the rectangle. From the vertex $(0,0)$ to $(n,n)$. Now, let's count the number of paths from lower left to upper right which come below this diagonal for the first time at the coordinate $(k,k)$. i.e., the path lies above the diagonal till it reaches $(k,k)$ then it moves to $(k+1,k)$, and then continues from there. The number of such paths are $C_k \binom{2n-2k}{2k}$ where $C_k$ is the $k^{th}$ Catalan number. (The number of paths from $(0,0)$ to $(k,k)$ that lie above the diagonal are $C_k$ and total paths from $(k+1,k)$ to $(n+1,n)$ are $\binom{2n-2k}{n-k}$. Taking the sum of this expression from $k= 0$ to $n$ gives the total number of paths from the lower left corner of the grid to the upper right corner. Thus, another expression for the same is $\sum_{k=0}^nC_k\binom{2n-2k}{n-k} = \sum_{k=0}^n\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k}$.

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

Solution 2:

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.