17
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Seems I am dumb today, but I don't see the first step here. $\endgroup$ – vonbrand Mar 4 '14 at 16:28
  • $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Mar 4 '14 at 17:12
4
$\begingroup$

$\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}

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel Dec 27 '16 at 22:10
  • $\begingroup$ @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. $\endgroup$ – Felix Marin Dec 29 '16 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.