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

Solution 1:

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

Solution 2:

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

Solution 3:

$$ \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, noting 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.