24
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you do it with generating functions? $\endgroup$ – Nikhil Ghosh Aug 8 '12 at 2:33
  • $\begingroup$ 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. $\endgroup$ – Emily Aug 8 '12 at 2:41
  • $\begingroup$ Wolfram|Alpha gives this closed form. $\endgroup$ – joriki Aug 8 '12 at 2:45
  • 2
    $\begingroup$ I don't really understand why combinatorial proof went more or less unnoticed (while standard application of generating functions is heavily upvoted). $\endgroup$ – Grigory M Nov 30 '13 at 13:28
37
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ty fixed it. I hope that was the only one :) $\endgroup$ – N. S. Aug 8 '12 at 2:51
10
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Ofir Jan 18 '13 at 16:31
  • $\begingroup$ @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. $\endgroup$ – Mike Spivey Jan 18 '13 at 18:56
  • $\begingroup$ 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? $\endgroup$ – Ofir Jan 19 '13 at 15:33
  • 2
    $\begingroup$ 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$. $\endgroup$ – darij grinberg Dec 20 '17 at 0:45
6
$\begingroup$

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

$\endgroup$

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.