# Closed form for two binomial identities

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

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

• My apologies, I didn't see the links present. Commented Mar 9, 2020 at 11:52
• Why do you expect that a purely direct algebraic solution would exist? A lot of these binomial summation identities come from combinatorial arguments or generating functions. Commented Mar 9, 2020 at 16:16

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