# proof of combinatorial identity using given identities

How does one prove $$\sum_{v} (-1)^v \binom {a} {v} \binom {n-v} {r}=\binom {n-a} {n-r}$$ where $$n,r$$ are positive integers, $$a$$ is arbitary real ,

using the given two identites. $$\binom {-a} {v}=(-1)^v\binom {a+v-1} {v}$$where $$a>0$$ is real and $$\binom {m} {0}\binom {l} {r}+\binom {m} {1}\binom {l} {r-1}+....\binom {m} {r}\binom {l} {0}=\binom {m+l} {r}$$

where $$m,l$$ are arbitary numbers and $$r$$ is a positive integer. I have been trying for a long time now. I can prove it using comparing degrees of certain terms in polynomials. But I don't see a way using the given identities.

• Are you sure that $\binom {-a} {v}=(-1)^v\binom {a+v-1} {v}$ for $a>0$? – Monadologie Jul 23 at 15:28
• @Monadologie Yes, isn't it? Am I overlooking something? – saulspatz Jul 23 at 15:40
• @ Monadologie yes. Its from Feller vol 1. – jnyan Jul 23 at 16:25

We obtain \begin{align*} \color{blue}{\sum_{\nu}}&\color{blue}{ (-1)^{\nu}\binom{a}{\nu}\binom{n-\nu}{r}}\\ &=\sum_{\nu} (-1)^{\nu} \binom{a}{\nu}\binom{n-\nu}{n-\nu-r}\tag{1}\\ &=(-1)^{n-r}\sum_{\nu} \binom{a}{\nu}\binom{-r-1}{n-\nu-r}\tag{2}\\ &=(-1)^{n-r}\binom{a-r-1}{n-r}\tag{3}\\ &\,\,\color{blue}{=\binom{n-a}{n-r}}\tag{4} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $$\binom{p}{q}=\binom{p}{p-q}$$.

• In (2) we use the binomial identity $$\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$$.

• In (3) we use the Chu-Vandermonde Identity $$\sum_{\nu}\binom{p}{\nu}\binom{q}{n-\nu}=\binom{p+q}{n}$$.

• In (4) we use again the binomial identity as we did in (2).

• thank you very much – jnyan Jul 25 at 5:56
• @jnyan: You're welcome. – Markus Scheuer Jul 25 at 6:22