I'd like to get a hint to prove the following identity:

$$\tag{1}\sum_{\nu}(-1)^{\nu}\displaystyle \binom{a}{\nu}\binom{n-\nu}{r}=\binom{n-a}{n-r} .$$

The original statement reads "By specialization derive from (12.9) the identity..." where (12.9) refers to:

$$\tag{2}\sum_{\nu}\binom{a}{\nu}\binom{b}{n-\nu}=\binom{a+b}{n}. $$

The problem suggests using $$\tag{3} \binom{-a}{k} = (-1)^k\binom{a+k-1}{k}.$$

I assumed that "by specialization" means "start with (2) and derive $(1)$", so I changed the sign of $a$ in (2), then I used $(3)$, but it didn't work or I don't know how to proceed from there, so I'd appreciate any help.


  • $\begingroup$ This might be from a source about probability, but the question itself is wholly about binomial coefficients and is self-contained without any reference to probability, so I am re-tagging and re-titling. Hope you don't mind Robert. $\endgroup$ – anon Feb 3 '12 at 3:59
  • 1
    $\begingroup$ This does look to be one of those things that cry out for Chu-Vandermonde... $\endgroup$ – J. M. isn't a mathematician Feb 3 '12 at 4:04
  • $\begingroup$ No, it's ok your re-tagging. Indeed, it's a problem from 'An Introduction to Probability Theory and Applications" (amazon.com/Introduction-Probability-Theory-Applications-Vol/dp/…) $\endgroup$ – Robert Smith Feb 3 '12 at 4:04
  • $\begingroup$ Can you specify the range of values for $v$ you're summing over? I assume that the sum is from $v=0$ to $v=a$, but it could also be from $v=1$ to $v=a$ or any number of other ranges. $\endgroup$ – Alex Becker Feb 3 '12 at 4:04
  • $\begingroup$ @AlexBecker Right, I forgot to mention it. It doesn't say (I know, it's annoying). I'm not so confident about this but a reasonable assumption could be $\nu$ from 0 to $a$ because of the first binomial. $\endgroup$ – Robert Smith Feb 3 '12 at 4:09

As long as both $n-\nu$ and $r$ are non-negative integers, we have $$ \begin{align} (-1)^\nu\binom{n-\nu}{r} &=(-1)^\nu\binom{n-\nu}{n-\nu-r}\\ &=(-1)^{n-r}\binom{-r-1}{n-\nu-r}\tag{1} \end{align} $$ Using $(1)$, we get $$ \begin{align} \sum_{\nu}(-1)^{\nu}\binom{a}{\nu}\binom{n-\nu}{r} &=(-1)^{n-r}\sum_{\nu}\binom{a}{\nu}\binom{-r-1}{n-\nu-r}\\ &=(-1)^{n-r}\binom{a-r-1}{n-r}\\ &=\binom{n-a}{n-r}\tag{2} \end{align} $$

| cite | improve this answer | |
  • $\begingroup$ Great, thank you very much. I was asking for a hint but now I see it was more or less elementary. Just a small correction: in (1), the exponent should be $(-1)^{n-r-\nu}$. $\endgroup$ – Robert Smith Feb 3 '12 at 18:03
  • $\begingroup$ I believe the exponent in $(1)$ is correct: $\binom{m}{k}=(-1)^k\binom{-m+k-1}{k}$. Set $m=n-\nu$ and $k=n-\nu-r$. (The way I remember this is that the sum of the tops is $1$ less than the bottom and the exponent of $-1$ is the bottom.) $\endgroup$ – robjohn Feb 3 '12 at 18:12
  • $\begingroup$ Oh, yes, I missed that you multiplied already $(-1)^{\nu}$ in (1). I thought you had multiplied implicitly starting (2). Thanks again :-) $\endgroup$ – Robert Smith Feb 3 '12 at 18:18

Well, let's see what do Mathematica say about this :

In:= Sum[(-1)^p*Binomial[a, p]*Binomial[n - p, r], {p, 0, a}]
Out= Binomial[-a + n, -a + r]

It looks like your statement is not true... (EDIT but of course it is true !)

Let's go for a proof. Let $f_{n,a,p,r}$ denote the expression $(-1)^p \binom{a}{p} \binom{n-p}{r}$, and $S_u$, the shift w.r.t. the variable $u$. For example, $(S_a f)_{n, a, p, r} = f_{n, a+1, p, r}$.

Let $g$ denote the sum $\sum_{p=0}^a f_{n,a,p,r}$, and $g'$ the expression $\binom{n-a}{r-a}$. We want to proof $g=g'$.

You can check that $$ \left((1+r)S_r+p+r-n\right)f + (S_p - 1)\left(\frac{-p - n p + p^2}{1 + r}f\right) = 0$$ When you sum, you get (notice the telescoping sum) $$ \left((1+r)S_r+p+r-n\right)g + \underbrace{\left[\frac{-p - n p + p^2}{1 + r}f\right]_{p=0}^{a+1}}_{=0} = 0$$

This gives you a recurrence for $g$, and it is easy to check that $g'$ satisfies the same.

You have similar formulas for the variables $n$ ans $r$. And you check that $g$ satisfies the defining recurrence equations of $g'$. And so $g=g'$.

These formulas can be found with the method of creative telescoping, which is implemented in Mathematica by the package HolonomicFunctions of Christoph Koutschan : you can prove this equality in a algorithmic way ! strong text

| cite | improve this answer | |
  • $\begingroup$ Um, $\binom{n-a}{r-a} = \binom{n-a}{n-a-(r-a)} = \binom{n-a}{n-r}$, by the symmetry of the binomial coefficients. So the statement is true. $\endgroup$ – Mike Spivey Feb 3 '12 at 17:17
  • $\begingroup$ @Lierre: I take for granted this is not the proof I was expected to work out but I will certainly take a closer look at this. Thanks! $\endgroup$ – Robert Smith Feb 3 '12 at 18:06
  • $\begingroup$ You're right Mike, of course ! I'm getting stupid when I use a computer, this is a problem ;) $\endgroup$ – Lierre Feb 3 '12 at 18:43

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.