# Double Binomial coefficient sum identity $S = \sum_{k = 0}^{n} (-1)^k {{4n-1-2k}\choose{2n-2k}}{{2n-1}\choose{k}}$

I have a sum of factorials that I managed to put in the following form $$S = \sum_{k = 0}^{n} (-1)^k {{4n-1-2k}\choose{2n-2k}}{{2n-1}\choose{k}}$$ where $$n\in\mathbb{N}$$. Mathematica can sum this object and it gives $$S = 2^{-1+2n}$$. Despite searching countless identities I haven't found a way to prove this result. I have also tried induction but it doesn't seem to be the right approach.

We use the coefficient of operator $$[z^k]$$ to denote the coefficient of $$z^k$$ of a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{(-1)^k\binom{4n-1-2k}{2n-2k}\binom{2n-1}{k}}\\ &=\sum_{k=0}^{2n-1}\binom{2n-1}{k}(-1)^k[z^{2n-2k}](1+z)^{4n-1-2k}\tag{2}\\ &=[z^{2n}](1+z)^{4n-1}\sum_{k=0}^{2n-1}\binom{2n-1}{k}(-1)^k\left(\frac{z}{1+z}\right)^{2k}\tag{3}\\ &=[z^{2n}](1+z)^{4n-1}\left(1-\frac{z^2}{(1+z)^2}\right)^{2n-1}\tag{4}\\ &=[z^{2n}](1+z)(1+2z)^{2n-1}\tag{5}\\ &=[z^{2n-1}](1+2z)^{2n-1}\tag{6}\\ &\,\,\color{blue}{=2^{2n-1}}\tag{7} \end{align*}

Comment:

• In (2) we apply the coefficient of operator according to (1). We also set the upper limit of the sum to $$2n-1$$ which does not change anything since $$\binom{4n-1-2k}{2n-2k}=0$$ if $$k>n$$.

• In (3) we apply the rule $$[z^{p-q}]A(z)=[z^p]z^qA(z)$$.

• In (4) we apply the binomial theorem.

• In (5) we do some simplifications.

• In (6) we observe the coefficient $$[z^{2n}](1+2z)^{2n-1}$$ is zero.

• In (7) we select the coefficient of $$z^{2n-1}$$.

• Nice work. (+1). – Marko Riedel May 20 '19 at 13:06
• @MarkoRiedel: Many thanks, Marko. :-) – Markus Scheuer May 20 '19 at 13:45

Yet another instance for these ideas... but this time the "pencil and paper" way is easier.

$$S$$ is the coefficient of $$x^{2n}$$ in (the power series expansion of) $$\left(\sum_{k=0}^{2n-1}(-1)^k\binom{2n-1}{k}x^{2k}\right)\left(\sum_{k=0}^{\infty}\binom{2n-1+k}{k}x^k\right)=(1-x^2)^{2n-1}(1-x)^{-2n}\\=\frac{(1+x)^{2n-1}}{1-x}=\frac{\big(2-(1-x)\big)^{2n-1}}{1-x}=\frac{2^{2n-1}}{1-x}-P(x),$$ where $$P(x)$$ is some polynomial of degree at most $$2n-2$$. The result follows.