Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$ + ... + $(-1)^n$${n}\choose{n}$$^2$

Thanks for any help.

share|improve this question
    
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. –  Arkamis Aug 8 '12 at 2:41
    
Wolfram|Alpha gives this closed form. –  joriki Aug 8 '12 at 2:45
1  
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
add comment

3 Answers 3

$$(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, he coefficient of $x^n$ is 0 if n odd or $(-1)^{\frac{n}2}{n \choose n/2}$ if $n$ is even.

share|improve this answer
1  
Great answer, but you've dropped a minus sign somewhere in your last sentence. Half the even values are negative and the other half are positive. –  Byron Schmuland Aug 8 '12 at 2:49
    
ty fixed it. I hope that was the only one :) –  N. S. Aug 8 '12 at 2:51
add comment

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

share|improve this answer
add comment

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)$. 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 $A + B = 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}$$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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