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

For context I am trying to prove the four identities:

$$\sum_{k\,\mathrm{even}} \binom{n}{k}^2 = \begin{cases} \frac{1}{2}\left( \binom{2n}{n}+(-1)^{n/2} \binom{n}{n/2} \right)\quad\mathrm{for}\,n\,\mathrm{even} \\ \frac{1}{2}\binom{2n}{n}\quad\mathrm{for}\,n\,\mathrm{odd}\end{cases}$$ $$\sum_{k\,\mathrm{odd}} \binom{n}{k}^2 = \begin{cases} \frac{1}{2}\left( \binom{2n}{n}-(-1)^{n/2} \binom{n}{n/2} \right)\quad\mathrm{for}\,n\,\mathrm{even} \\ \frac{1}{2}\binom{2n}{n}\quad\mathrm{for}\,n\,\mathrm{odd}\end{cases}$$

The cases for $$n$$ odd are easy, since it can be interpreted as choosing a subset of $$n$$ coins from a bag of $$n$$ gold and $$n$$ silver coins, and demanding a fixed parity of the gold (and hence) silver coins, and observing that each possible choice of $$n$$ coins maps onto the choice of the complementary set of $$n$$ coins when the parity is fixed to be the other choice.

No such simple bijection exists for the case where $$n$$ is even, so I am not sure how to modify the scenario to yield a double counting solution to the problem.

I am open to a solution that involves counting paths on a square lattice of size $$n$$.

• For a straightforward algebraic solution, consider the $x^n$ term of $(1-x)^n(1+x)^n$. It’s not clear how to turn that into combinatorics terms (maybe look at parity after pairing up silver, gold coins?)
– Eric
Commented Jul 26, 2021 at 15:43
• It would follow from $\sum_k(-1)^k\binom{n}{k}^2 = (-1)^{n/2}\binom{n}{n/2}$. I've tried to come up with an inclusion-exclusion argument, but the closest I've come is $\sum_{k=0}^n (-1)^k\binom{n}{k}\binom{m+n-k}{r-k} = \binom{m}{r}$, for what it's worth. To see it, take $n$ gold and $m$ silver balls, and draw $r$ of these. Then count the number of draws that avoid all gold balls. I don't know, maybe someone else can use this as inspiration somehow. Commented Jul 28, 2021 at 11:47

Choose a subset of $$n$$ coins from a bag of $$n$$ gold coins $$g_1, \dotsc, g_n$$ and $$n$$ silver coins $$s_1, \dotsc, s_n$$. Of the $$\binom{2n}{n}$$ ways to do this, there are $$\binom nk^2$$ ways such that you got $$k$$ gold coins and $$n - k$$ silver coins.

$$\sum_{\text{k even}} \binom nk^2 + \sum_{\text{k odd}} \binom nk^2 = \binom{2n}{n}.$$

Try to transform your choice as follows: let $$i$$ be the smallest index such that you chose exactly one of $$g_i$$ or $$s_i$$, and swap it for the other one instead. This transformation is self-inverse, and toggles the parity of $$k$$. The only exception is if there is no such index, because your gold choices were identical to your silver choices—which requires $$n = 2k$$, and can then happen in $$\binom{n}{n/2}$$ ways.

$$\sum_{\text{k even}} \binom nk^2 - \sum_{\text{k odd}} \binom nk^2 = \begin{cases}(-1)^{n/2}\binom{n}{n/2} & \text{for n even} \\ 0 & \text{for n odd}.\end{cases}$$

The identities follow.

• while nice, this isn't the kind of answer i'm after. sorry. Commented Oct 3, 2021 at 10:14
• @JackTigerLam Really? It’s exactly the strategy you used for the $n$ odd case, except with a different transformation that swaps a single coin instead of swapping all coins. What other kind of answer are you looking for? Commented Oct 3, 2021 at 10:19
• This proof gives a slight generalization: $\sum_k\binom{n}{k}\binom{n}{m-k} = \binom{2n}{m}$, $\sum_k(-1)^k\binom{n}{k}\binom{n}{m-k} = (-1)^{m/2}\binom{n}{m/2}$, with $\binom{n}{m/2}:=0$ for odd $m$. And this of course gives formulae for the odd and even sums. Commented Oct 4, 2021 at 7:19