Closed form for two binomial identities

Question

Can someone provide a direct algebraic solution to prove the following identity:

$$\sum_{k=0}^{n}\binom{2k}{k}\binom{2n-2k}{n-k}=4^n$$

These are the links about this question:

$1$

$2$

$3$

$4$

$5$

All of the answers use combinatorial interpretation or generating function (indeed none of the algebraic ways I've ever seen were direct and they all uses some default facts). With direct algebraic solution I mean a solution which begins from the LHS and derives the RHS.

I tried Hagen and Rothe identity which states :

$$\sum_{k=0}^{n}\binom{r-tk}{k}\binom{s-t \left(n-k\right)}{n-k}\frac{r}{r-tk}=\binom{r+s-tn}{n}$$

Setting $t=-2,r=1,s=0$ we get:

$$\sum_{k=0}^{n}\binom{2k+1}{k}\binom{2 \left(n-k\right)}{n-k}\frac{1}{2k+1}=\sum_{k=0}^{n}\binom{2k+1}{k+1}\binom{2 \left(n-k\right)}{n-k}\frac{1}{2k+1}$$$$=\sum_{k=0}^{n}\binom{2k}{k}\binom{2 \left(n-k\right)}{n-k}\frac{1}{k+1}$$

---

The other one is:

$$\sum_{k=0}^{n}\binom{n+k}{k}\binom{n}{k}\frac{\left(-1 \right)^k}{k+1+m}$$

I determined a closed form for this identity when $m=0$ , but I don't know how to start with this one.

Answer 1

Note that for any real $ \alpha $ : $$ \left(\forall x\in\left]-1,1\right[\right),\ \displaystyle\sum_{n=0}^{+\infty}{\displaystyle\binom{\alpha}{n}x^{n}}=\left(1+x\right)^{\alpha} $$ Thus, for $ x\in\left]-1,1\right[ $ : $$ \displaystyle\sum_{n=0}^{+\infty}{\left(-1\right)^{n}\displaystyle\binom{-\frac{1}{2}}{n}x^{n}}=\displaystyle\frac{1}{\sqrt{1-x}} \ \ \ \ \left(*\right) $$ Observe that : $$ \left(\forall n\in\mathbb{N}\right),\ \left(-1\right)^{n}\displaystyle\binom{-\frac{1}{2}}{n}=\displaystyle\frac{\left(-1\right)^{n}}{n!}\displaystyle\prod_{k=0}^{n-1}{\left(-\displaystyle\frac{1}{2}-k\right)}=\displaystyle\frac{1}{2^{n}n!}\displaystyle\prod_{k=0}^{n-1}{\left(2k+1\right)}=\displaystyle\frac{1}{4^{n}}\displaystyle\binom{2n}{n} $$ Multiplying the expression $ \left(*\right) $ by itself gives the following : $$ \displaystyle\sum_{n=0}^{+\infty}{\displaystyle\frac{1}{4^{n}}\left(\displaystyle\sum_{k=0}^{n}{\displaystyle\binom{2k}{k}\displaystyle\binom{2n-2k}{n-k}}\right)x^{n}}=\displaystyle\frac{1}{1-x}=\displaystyle\sum_{n=0}^{+\infty}{x^{n}} $$ Then we get the result : $$ \left(\forall n\in\mathbb{N}\right),\ \displaystyle\sum_{k=0}^{n}{\displaystyle\binom{2k}{k}\displaystyle\binom{2n-2k}{n-k}}=4^{n} $$