10
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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?) $\endgroup$
    – Eric
    Commented Jul 26, 2021 at 15:43
  • $\begingroup$ 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. $\endgroup$
    – Milten
    Commented Jul 28, 2021 at 11:47

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ while nice, this isn't the kind of answer i'm after. sorry. $\endgroup$ Commented Oct 3, 2021 at 10:14
  • 2
    $\begingroup$ @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? $\endgroup$ Commented Oct 3, 2021 at 10:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Milten
    Commented Oct 4, 2021 at 7:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .