2
$\begingroup$

How to find compact form of the sum $$\sum\limits_{k=0}^m (-1)^k \binom{n}{k} \binom{n}{m-k}$$

It looks like it's connected with Vandermonde's identity but I couldn't get to the solution.

$\endgroup$
  • $\begingroup$ You mean the sum for the index $k$ and $i$ $\endgroup$ – marwalix Apr 4 '15 at 18:48
  • $\begingroup$ You can write the sum in terms of hypergeometric function. $\endgroup$ – Marco Cantarini Apr 4 '15 at 18:59
3
$\begingroup$

Note that, in $(1-x^2)^n=(1-x)^n(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}(-x)^k\cdot \sum_{k=0}^{n}\binom{n}{k}x^k$. Consider the coefficient of $x^m$, for odd $m$, we get $\sum_{k=0}^n (-1)^k\binom{n}{k}\binom{n}{m-k}=0$, for even $m$, we get $\sum_{k=0}^n (-1)^k\binom{n}{k}\binom{n}{m-k}=(-1)^{\frac{m}{2}}\binom{n}{\frac{m}{2}}$.

$\endgroup$
2
$\begingroup$

Since $$ \sum_{k=0}^{n}\binom{n}{k}(-x)^k = (1-x)^n,\tag{1}$$ $$ \sum_{k=0}^{n}\binom{n}{k}x^k = (1+x)^n,\tag{2} $$ we have: $$ \sum_{k=0}^{n}\binom{n}{k}\binom{n}{m-k}(-1)^k = [x^m](1-x)^n(1+x)^n = [x^m](1-x^2)^n \tag{3}$$ hence:

$$ \sum_{k=0}^{n}\binom{n}{k}\binom{n}{m-k}(-1)^k = \left\{\begin{array}{rcl}0&\text{if}& m\text{ is odd}\\(-1)^{\frac{m}{2}}\binom{n}{\frac{m}{2}}&\text{if}& m\text{ is even.}\end{array}\tag{4}\right.$$

$\endgroup$
  • $\begingroup$ I don't quite understand the (3) step. How did you get this equation? Could you explain it a bit more? $\endgroup$ – VirrageS Apr 4 '15 at 19:29
  • 1
    $\begingroup$ Never mind. I get it now. Thanks so much. $\endgroup$ – VirrageS Apr 4 '15 at 19:45
  • $\begingroup$ Very nice solution! I wonder if there exists a solution which uses only the binomial coefficients and/or their identities. $\endgroup$ – hypergeometric Apr 6 '15 at 15:15
2
$\begingroup$

This question can be treated using basic complex variables, which is an instructive exercise (it so happens that in this particular case the procedure is very similar to the answers from the first responders but this is not always so).

Suppose we seek to compute $$\sum_{k=0}^m (-1)^k {n\choose k} {n\choose m-k}$$ with $n$ a positive integer.

Introduce the integral representation $${n\choose m-k} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{m-k+1}} \; dw.$$

Observe that the integral is zero when $k\gt m$ so we may extend the sum to infinity. This yields for the sum

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{m+1}} \sum_{k=0}^\infty {n\choose k} (-1)^k w^k\; dw.$$

This is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{m+1}} (1-w)^n \; dw = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1-w^2)^{n}}{w^{m+1}} \; dw.$$

Therefore the sum is $$[w^m] (1-w^2)^n$$ which is $$(-1)^{m/2} {n\choose m/2}$$ if $m$ is even and zero otherwise.

This MSE link shows an actual gain from the complex variables procedure.

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