Binomial identity

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.

Thanks!

• 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. – anon Feb 3 '12 at 3:59
• This does look to be one of those things that cry out for Chu-Vandermonde... – J. M. is a poor mathematician Feb 3 '12 at 4:04
• 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/…) – Robert Smith Feb 3 '12 at 4:04
• 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. – Alex Becker Feb 3 '12 at 4:04
• @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. – 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}

• 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}$. – Robert Smith Feb 3 '12 at 18:03
• 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.) – robjohn Feb 3 '12 at 18:12
• Oh, yes, I missed that you multiplied already $(-1)^{\nu}$ in (1). I thought you had multiplied implicitly starting (2). Thanks again :-) – Robert Smith Feb 3 '12 at 18:18

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

• 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. – Mike Spivey Feb 3 '12 at 17:17
• @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! – Robert Smith Feb 3 '12 at 18:06
• You're right Mike, of course ! I'm getting stupid when I use a computer, this is a problem ;) – Lierre Feb 3 '12 at 18:43