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!
 A: 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}
$$
A: 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
