# Show that $\sum\limits_{k=0}^n\binom{2n}{2k}^{\!2}-\sum\limits_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove the identity: $$\sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}?$$

Maybe, can we expand $$f(x)=(1+x)^{2n}?$$

Thank you.

Idea. We shall obtain the identity by equating the coefficient of $x^{2n}$ in the expansions of $(1+x^2)^{2n}$ and $(1+ix)^{2n}(1-ix)^{2n}$.

The binomial expansion of $(1+x^2)^{2n}$ is $$(1+x^2)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^{2k},$$ while $$(1+x^2)^{2n}=(1+ix)^{2n}(1-ix)^{2n}=\left(\sum_{k=0}^{2n}\binom{2n}{k}(ix)^{k}\right)\left(\sum_{k=0}^{2n}\binom{2n}{k}(-ix)^{k}\right).$$ The coefficient of $x^{2n}$ in the first expansion is $a_{2n}=\displaystyle\binom{2n}{n}$, while in the right-hand side of the above it can be expressed as the following sum: \begin{align} a_{2n}&=\sum_{k=0}^{2n}i^k(-i)^{2n-k}\binom{2n}{k}\binom{2n}{2n-k}=i^{2n} \sum_{k=0}^{2n}(-1)^{k}\binom{2n}{k}\binom{2n}{k} \\&=(-1)^{n} \sum_{k=0}^{2n}(-1)^{k}\binom{2n}{k}^{\!2}= (-1)^{n}\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^{\!2}\\ &= (-1)^{n}\sum_{k=0}^{n}\binom{2n}{2k}^{\!2}-(-1)^{n}\sum_{k=1}^{n-1}\binom{2n}{2k-1}^{\!2}\!\!. \end{align} Hence $$\sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}.$$

• sorry but in the 3rd last line the sum on the right goes from 1 to n not ? – OBDA Mar 4 '14 at 16:39
• I think this is unnecessarily complicated – Marc van Leeuwen Mar 4 '14 at 20:08

This is simpler if you rewrite your left hand side as $$\sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2= \sum_{i=0}^{2n}(-1)^i\binom{2n}i^2= \sum_{i=0}^{2n}(-1)^i\binom{2n}i\binom{2n}{2n-i}$$ first. So you are looking for the coefficient of $X^{2n}$ in the product $(1-X)^{2n}(1+X)^{2n}=(1-X^2)^{2n}$, which is the same as the coefficient of $Y^n$ in $(1-Y)^{2n}$. That coefficient is clearly $(-1)^n\binom{2n}n$.

Note that one could replace $2n$ by $m$ and allow it to be odd, if one takes the right hand side to be$~0$ in that case. The proof remains the same, remarking that there is obviously no term $X^m$ in $(1-X^2)^m$ when $m$ is odd.

Let me also give a combinatorial proof (since that tag is given). Given $m$ mixed-sex couples, the left hand side counts the number of gender-balanced subsets (containing equally many women as men), counted with a factor$~{-}1$ if that number for each sex is odd. In this counting, the subsets that do not contain exactly one member of each couple cancel out as follows: for such a subset, find the first couple of which which not exactly one member was selected, and add or remove the couple to obtain a cancelling subset; this operation is clearly a gender parity respecting involution. So we are left with as un-cancelled contributions those from the gender-balanced subsets with one member from each couple, which subsets are clearly of size$~m$. If $m$ is odd then no subsets at all remain, as gender balance is impossible. If $m$ is even then each remaining gender-balanced subset is counted with sign $(-1)^{m/2}$and it is determined by the $m/2$ women it contains (it is completed by the men from the other $m/2~$couples), so there are $\binom m{m/2}$ of them.

• Seems I am dumb today, but I don't see the first step here. – vonbrand Mar 4 '14 at 16:28
• @vonbrand: There is an intermediate form $\sum_{k=0}^{2n}(-1)^k\binom{2n}k^2$, which is just recognising that the squares of a whole row of Pascal's triangle are present in the two sums, with alternating signs. Then separate the two factors in $\binom{2n}k^2$, and apply symmetry to one of them. – Marc van Leeuwen Mar 4 '14 at 17:12

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\sum_{k = 0}^{n}{2n \choose 2k}^{2} -\sum_{k = 0}^{n - 1}{2n \choose 2k + 1}^{2} = \pars{-1}^{n}{2n \choose n}: \ {\large ?}}$.

$$\mbox{Note that}\quad \sum_{k = 0}^{n}{2n \choose 2k}^{2} - \sum_{k = 0}^{n - 1}{2n \choose 2k + 1}^{2} =\sum_{k = 0}^{2n}\pars{-1}^{k}{2n \choose k}^{2}$$

\begin{align}&\color{#66f}{\large\sum_{k = 0}^{n}{2n \choose 2k}^{2} -\sum_{k = 0}^{n - 1}{2n \choose 2k + 1}^{2}} =\sum_{k = 0}^{2n}{2n \choose k}\pars{-1}^{k} \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \\[6mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z} \sum_{k = 0}^{2n}{2n \choose k}\pars{-\,{1 \over z}}^{k}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z} \,\bracks{1 + \pars{-\,{1 \over z}}}^{2n}\,{\dd z \over 2\pi\ic} \\[6mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 - z^{2}}^{2n} \over z^{2n + 1}} \,{\dd z \over 2\pi\ic} =\sum_{k = 0}^{2n}{2n \choose k}\pars{-1}^{k}\ \underbrace{\oint_{\verts{z}\ =\ 1}{1 \over z^{2n - 2k + 1}}% \,{\dd z \over 2\pi\ic}}_{\ds{=\ \color{#c00000}{\large\delta_{kn}}}} \\[6mm]&=\sum_{k = 0}^{2n}{2n \choose k}\pars{-1}^{k}\,\delta_{kn} =\color{#66f}{\large\pars{-1}^{n}{2n \choose n}} \end{align}

• I upvoted this the first time I saw it and one may only upvote once. I believe you were one of the first MSE users to present the Egorychev method, which I use frequently, influenced by your work. – Marko Riedel Dec 27 '16 at 22:10
• @MarkoRiedel Thanks. It's a quite powerful method. At the beginning, I didn't know it already has a name. Sometimes ago, I started writing Kronecker's Delta by means of 'complex integrals' in some physics problem which is loosely related to this approach. – Felix Marin Dec 29 '16 at 20:30