Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
1  
This does look to be one of those things that cry out for Chu-Vandermonde... –  J. M. 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
show 3 more comments

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.