Prove: $\sum\limits_{k=0}^{n}\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k} = \binom{2n+1}{n}$ prove the following identity:
$\displaystyle\sum_{k=0}^{n}\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k} = \binom{2n+1}{n}$
what I tried:
I figured that: $\displaystyle\binom{2n+1}{n} = (2n+1) C_n$
and $\displaystyle\sum_{k=0}^{n}\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k}= \sum_{k=0}^{n}C_k\binom{2n-2k}{n-k}$
from here i tried simplifying:$\displaystyle\binom{2n-2k}{n-k}$ to something i could work with but did not succeed
I also know that $\displaystyle C_n = \sum_{k=0}^{n-1}C_k C_{n-k-1}$ so I tried to prove : $\displaystyle\sum_{k=0}^{n}C_k\binom{2n-2k}{n-k}= C_n + \sum_{k=0}^{n-1}C_k\binom{2n-2k}{n-k} = C_n + 2n\sum_{k=0}^{n-1}C_kC_{n-k-1}$ but that approach also failed (couldn't prove the last equality)
any suggestions?
 A: This is
$$\sum_{k=0}^n C_kA_{n-k}=B_n\tag{*}$$
where
$$C_n=\frac1{n+1}\binom{2n}{n},$$
$$A_n=\binom{2n}{n}$$
and
$$B_n=\binom{2n+1}{n}.$$
All we need to confirm (*) is to prove the generating function identity
$$C(x)A(x)=B(x)$$
where $A(x)=\sum_{n=0}^\infty A_n x^n$ etc.
But
$$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$
and
$$A(x)=\frac1{\sqrt{1-4x}}$$
so that
$$C(x)A(x)=\frac1{2x\sqrt{1-4x}}-\frac12
=\frac12\sum_{m=1}^\infty\binom{2m}mx^{m-1}
=\frac12\sum_{n=0}^\infty\binom{2n+2}{n+1}x^n$$
so all we now need is
$$\binom{2n+1}n=\frac12\binom{2n+2}{n+1}.$$
A: Here’s a combinatorial argument. $\binom{2n+1}n$ is the number of lattice paths from $\langle 0,0\rangle$ to $\langle n,n+1\rangle$ using $n$ right steps and $n+1$ up steps. Every such path must rise above the line $y=x$; let $\langle k,k+1\rangle$ be the first point at which it does so. There are $C_k=\frac1{k+1}\binom{2k}k$ paths from $\langle 0,0\rangle$ to $\langle k,k\rangle$ that do not rise above the line $y=x$, any of which can be combined with any of the $\binom{2n-2k}{n-k}$ unrestricted lattice paths from $\langle k,k+1\rangle$ to $\langle n,n+1\rangle$, so there are $\frac1{k+1}\binom{2k}k\binom{2n-2k}{n-k}$ paths from $\langle 0,0\rangle$ to $\langle n,n+1\rangle$ that first rise above the line $y=x$ at $\langle k,k+1\rangle$. Summing over $k$ yields the desired result.
