Sum of binomial coefficients

[hxthanh]

Evaluate sum:

$\displaystyle S=\sum_{k=0}^{2n}(-1)^k{2n\choose k}{4n\choose 2k}$

 

[Opalg]

Evaluate sum:

$\displaystyle S_n=\sum_{k=0}^{2n}(-1)^k{2n\choose k}{4n\choose 2k}$

I believe that the answer must be \(\displaystyle S = \frac{(-1)^n(6n)!(2n)!}{(4n)!(3n)!n!}\), but I have NO idea how one might prove that.

What I did was to calculate $S_n$ when $n=1,\,2,\,3$, and then look those numbers up in the OEIS. This gave the above formula, and suggested that the next result, when $n=4$, would be $104006$. I then laboriously calculated $S_4$, and found that it is indeed $104006$. So my proposed formula has predictive value and therefore must be correct. Now perhaps somebody can tell me why.

 

[hxthanh]

I believe that the answer must be \(\displaystyle S = \frac{(-1)^n(6n)!(2n)!}{(4n)!(3n)!n!}\), but I have NO idea how one might prove that.
...

Your result is absolute correct!
Hint:

Spoiler

$(1-x^2)^m(1+x)^{2m}=(1-x)^m(1+x)^{3m}$

Good luck!

 

[hxthanh]

My solution

Spoiler

We start from the formula $(1-x^2)^m(1+x)^{2m}=(1-x)^m(1+x)^{3m}$
Now applying the binomial theorem
We have: $$ \sum_{k=0}^m (-1)^k{m\choose k}x^{2k} \sum_{j=0}^{2m} {2m\choose j}x^j = \sum_{k=0}^m (-1)^k{m\choose k}x^k \sum_{j=0}^{3m} {3m\choose j}x^j$$

\begin{equation} \label{eq1}\tag{1}\Leftrightarrow \sum_{k=0}^m \sum_{j=0}^{2m}(-1)^k {m\choose k} {2m\choose j}x^{2k+j} = \sum_{k=0}^m \sum_{j=0}^{3m} (-1)^k {m\choose k}{3m\choose j}x^{k+j} \end{equation}
compare coefficient of $x^{2m}$ in $\eqref{eq1} $ then we get
$\displaystyle \quad\sum_{2k+j=2m}(-1)^k {m\choose k} {2m\choose j}=\sum_{k+j=2m}(-1)^k {m\choose k} {3m\choose j}$
$\displaystyle \Leftrightarrow \sum_{k=0}^m(-1)^k {m\choose k} {2m\choose 2m-2k}=\sum_{k=0}^m (-1)^k {m\choose k} {3m\choose 2m-k}$
$\displaystyle \Leftrightarrow \sum_{k=0}^m(-1)^k {m\choose k} {2m\choose 2k}=\sum_{k=0}^m (-1)^k {m\choose k} {3m\choose m+k}$

with $m=2n$ then
\begin{equation} \label{eq2} \begin{aligned} S&=\sum_{k=0}^{2n}(-1)^k {2n\choose k} {4n\choose 2k}=\sum_{k=0}^{2n} (-1)^k {2n\choose k} {6n\choose 2n+k} \\ &=\sum_{k=0}^{2n} \dfrac{(-1)^k(2n)!(6n!)}{k!(2n-k)!(2n+k)!(4n-k)!} \\ &=\dfrac{(2n)!(6n)!}{(4n)!(4n)!} \sum_{k=0}^{2n} \dfrac{(-1)^k(4n)!(4n!)}{k!(4n-k)!(2n+k)!(2n-k)!} \\ &= \dfrac{(2n)!(6n)!}{(4n)!(4n)!} \sum_{k=0}^{2n} (-1)^k {4n\choose k} {4n\choose 2n-k} \\ &= \dfrac{(2n)!(6n)!}{(4n)!(4n)!} \sum_{k+j=2n} (-1)^k {4n\choose k} {4n\choose j}\tag{2} \end{aligned} \end{equation}
next to formula $(1-x^2)^{4r}=(1-x)^{4r}(1+x)^{4r}$
we get $ \displaystyle \sum_{k=0}^{4r}(-1)^k {4r\choose k}x^{2k}=\sum_{k=0}^{4r} \sum_{j=0}^{4r} (-1)^k {4r\choose k} {4r\choose j}x^{k+j}$
now, compare coefficient of $x^{2r}$ in that then we get
\begin{equation} \label{eq3}\tag{3} (-1)^r {4r\choose r}=\sum_{k+j=2r}(-1)^k {4r\choose k} {4r\choose j}\end{equation}
From $\eqref{eq2}$ and $\eqref{eq3}$, we have:
$$S=\dfrac{(2n)!(6n)!}{(4n)!(4n)!}\cdot(-1)^n{4n\choose n}=\dfrac{(-1)^n(2n)!(6n)!}{n!(3n)!(4n)!}$$