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