# Alternating sum of squares of binomial coefficients

I know that the sum of squares of binomial coefficients is just $${2n}\choose{n}$$ but what is the closed expression for the sum $${n\choose 0}^2 - {n\choose 1}^2 + {n\choose 2}^2 + \cdots + (-1)^n {n\choose n}^2$$?

• Can you do it with generating functions? – Nikhil Ghosh Aug 8 '12 at 2:33
• I thought I had something clever. I have deleted my post until I have a chance to think on the case when $n$ is even. $n$ being odd still yields 0, unless I am totally mistaken. – Emily Aug 8 '12 at 2:41
• Wolfram|Alpha gives this closed form. – joriki Aug 8 '12 at 2:45
• I don't really understand why combinatorial proof went more or less unnoticed (while standard application of generating functions is heavily upvoted). – Grigory M Nov 30 '13 at 13:28

$$(1+x)^n(1-x)^n=\left( \sum_{i=0}^n {n \choose i}x^i \right)\left( \sum_{i=0}^n {n \choose i}(-x)^i \right)$$

The coefficient of $$x^n$$ is $$\sum_{k=0}^n {n \choose n-k}(-1)^k {n \choose k}$$ which is exactly your sum.

On another hand:

$$(1+x)^n(1-x)^n=(1-x^2)^n=\left( \sum_{i=0}^n {n \choose i}(-1)^ix^{2i} \right)$$

Thus, the coefficient of $$x^n$$ is $$0$$ if $$n$$ is odd or $$(-1)^{\frac{n}2}{n \choose n/2}$$ if $$n$$ is even.

• ty fixed it. I hope that was the only one :) – N. S. Aug 8 '12 at 2:51

Here's a combinatorial proof.

Since $\binom{n}{k} = \binom{n}{n-k}$, we can rewrite the sum as $\sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} (-1)^k$. Then $\binom{n}{k} \binom{n}{n-k}$ can be thought of as counting ordered pairs $(A,B)$, each of which is a subset of $\{1, 2, \ldots, n\}$, such that $|A| = k$ and $|B| = n-k$. The sum, then, is taken over all such pairs such that $|A| + |B| = n$.

Given $(A,B)$, let $x$ denote the largest element in the symmetric difference $A \oplus B = (A - B) \cup (B - A)$ (assuming that such an element exists). In other words, $x$ is the largest element that is in exactly one of the two sets. Then define $\phi$ to be the mapping that moves $x$ to the other set. The pairs $(A,B)$ and $\phi(A,B)$ have different signs, and $\phi(\phi(A,B)) = (A,B)$, so $(A,B)$ and $\phi(A,B)$ cancel each other out in the sum. (The function $\phi$ is what is known as a sign-reversing involution.)

So the value of the sum is determined by the number of pairs $(A,B)$ that do not cancel out. These are precisely those for which $\phi$ is not defined; in other words, those for which there is no largest $x$. But there can be no largest $x$ only in the case $A=B$. If $n$ is odd, then the requirement $\left|A\right| + \left|B\right| = n$ means that we cannot have $A=B$, so in the odd case the sum is $0$. If $n$ is even, then the number of pairs is just the number of subsets of $\{1, 2, \ldots, n\}$ of size $n/2$; i.e., $\binom{n}{n/2}$, and the parity is determined by whether $|A| = n/2$ is odd or even.

Thus we get $$\sum_{k=0}^n \binom{n}{k}^2 (-1)^k = \begin{cases} (-1)^{n/2} \binom{n}{n/2}, & n \text{ is even}; \\ 0, & n \text{ is odd}.\end{cases}$$

• Wonderful proof, Mike! I always prefer combinatorial proofs as they also offer motivation and explanation to the identity and not only a formal proof. What really interests me is whether you can construct a sign-reversing involution to prove the following special case of Dixon's Identity: $\sum_{k=0}^{n} \binom{3n}{k}^{3}(-1)^{k} = (-1)^n\binom{3n}{n,n,n}$. – Ofir Jan 18 '13 at 16:31
• @Ofir: I'm glad you like it! I'm a big fan of combinatorial proofs myself. That's an interesting question about Dixon's identity; you should ask it as a question on the site. – Mike Spivey Jan 18 '13 at 18:56
• I can't edit my original comment, but in the LHS it should be $\binom{2n}{k}^{3}$ instead of $\binom{3n}{k}^{3}$. Reading an article by Zeliberger, I found out there's a combinatorial proof for Dixon's identity by Foata. It should be in the following French book: www-irma.u-strasbg.fr/~foata/paper/ProbComb.pdf . I think pages 37-40 generalize it but I don't know any French, can anyone help out? – Ofir Jan 19 '13 at 15:33
• A belated comment: Your beautiful proof can be easily extended to the more general result that $\sum\limits_{k=0}^n \dbinom{m}{k} \dbinom{m}{n-k} \left(-1\right)^k = \begin{cases} \left(-1\right)^{n/2} \dbinom{m}{n/2} , & \text{ if } n \text{ is even}; \\ 0 , & \text{ if } n \text{ is odd} \end{cases}$ for any nonnegative integers $m$ and $n$. – darij grinberg Dec 20 '17 at 0:45

$$\sum_{m=0}^n (-1)^m{n \choose m}^2= (n!)^2\sum_{m=0}^n \frac{(-1)^m}{(m!)^2((n-m)!)^2}$$

This function feels hypergeometric, so we take the quotient of $c_{m+1}$ and $c_m$ where

$$c_m=\frac{(n!)^2}{(m!)^2((n-m)!)^2}$$

so,

$$\frac{c_{m+1}}{c_{m}}=\frac{((m+1)!)^2((n-m-1)!)^2}{(m!)^2((n-m)!)^2}=\frac{(m-n)^2}{(m+1)^2}$$

after some simplification, confirming that this can be expressed in terms of a hypergeometric function. The previous result gives us the parameters of the function so we find $\sum_{m=0}^\infty c_m x^m = {_2}F_1(-n, -n; 1;-1)$.

$${_2}F_1(-n, -n; 1;-1)= \sum_{m=0}^\infty \frac{((-n)_m)^2}{(1)_k} \frac{(-1)^k}{k!} = \sum_{m=0}^\infty (-1)^m{n \choose m}^2$$

Where $(x)_n=x(x+1)\cdots(x+n-1)=\frac{\Gamma(x+n)}{\Gamma(x)}$ is Pochhammer's symbol.

An identity for ${_2}F_1$ gives an elegant "closed form:"

$${_2}F_1(-n, -n; 1;-1)= \frac{2^{n} \sqrt{\pi} \Gamma(-n+n+1)}{\Gamma\left(\frac{1-n}{2}\right)\Gamma\left(\frac{-n}{2}+n+1\right)}= \frac{2^{n} \sqrt{\pi}}{\Gamma\left(\frac{1-n}{2}\right)\Gamma\left(\frac{n+2}{2}\right)}$$

Now, nothing that if $a$ is a positive integer, ${n \choose n+a}=0$, so

$$\sum_{m=0}^\infty (-1)^m{n \choose m}^2 = \sum_{m=0}^n (-1)^m{n \choose m}^2$$

and finally we get the answer

$$\sum_{m=0}^n (-1)^m{n \choose m}^2=\frac{2^{n} \sqrt{\pi}}{\Gamma\left(\frac{1-n}{2}\right)\Gamma\left(\frac{n+2}{2}\right)}$$

that holds for real numbers as well.