Prove: $\sum\limits_{k=0}^{n}\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k} = \binom{2n+1}{n}$

Question

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?

Answer 1

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.

Answer 2

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}.$$