# 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 + ... + (-1)^n$${n}\choose{n}$$^2 Thanks for any help. - 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 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 ## 3 Answers 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}$$- 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$$ \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. -$$(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.

-
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