8
$\begingroup$

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!

  • 0
    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.2012-02-03
  • 1
    This does look to be one of those things that cry out for Chu-Vandermonde...2012-02-03
  • 0
    No, it's ok your re-tagging. Indeed, it's a problem from 'An Introduction to Probability Theory and Applications" (http://www.amazon.com/Introduction-Probability-Theory-Applications-Vol/dp/0471257087)2012-02-03
  • 0
    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.2012-02-03
  • 0
    @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.2012-02-03
  • 0
    @J.M. Certainly looks like that identity (which I didn't know) could help, although I'm probably 'not allowed' to use it (by the way, this is self-study but using that identity would be 'too much' help :-))2012-02-03
  • 0
    It isn't too difficult to prove Chu-Vandermonde from first principles if need be. Have you seen "Concrete Mathematics"? You might want to study the route taken in that book for Chu-Vandermonde.2012-02-03
  • 0
    @J.M. Now I see. It gives a nice combinatorial explanation (page 170, for those interested). Even so, I'd like to know what Feller had in mind for proving it, but thanks for that.2012-02-03

2 Answers 2

5

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} $$

  • 0
    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}$.2012-02-03
  • 0
    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.)2012-02-03
  • 0
    Oh, yes, I missed that you multiplied already $(-1)^{\nu}$ in (1). I thought you had multiplied implicitly starting (2). Thanks again :-)2012-02-03
1

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

  • 0
    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.2012-02-03
  • 0
    @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!2012-02-03
  • 0
    You're right Mike, of course ! I'm getting stupid when I use a computer, this is a problem ;)2012-02-03