# Sum of binomial coefficients

#### hxthanh

##### New member
Evaluate sum:

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

#### Opalg

##### MHB Oldtimer
Staff member
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

##### New member
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:
$(1-x^2)^m(1+x)^{2m}=(1-x)^m(1+x)^{3m}$

Good luck!

#### hxthanh

##### New member
My solution
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$$

$$\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}$$
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
\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}
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
$$\label{eq3}\tag{3} (-1)^r {4r\choose r}=\sum_{k+j=2r}(-1)^k {4r\choose k} {4r\choose j}$$
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)!}$$

Last edited: