How do I show that $ \sum_{r=0}^q {n \choose q-r} {n-q+r \choose r}(-1)^r = 0 $? [duplicate]

Question

I am hoping to show that

$$ \sum_{r=0}^q {n \choose q-r} {n-q+r \choose r}(-1)^r = 0 $$

for integers $n \geq 1$ and $1 \leq q \leq n$.

I've worked out a few examples and it seems reasonable that it should hold, but I've been unable to prove it in the general case. I've seen identities around and tried rewriting as

$$ \sum_{r=0}^q {n \choose r} {n-r \choose n-q}(-1)^r = 0 $$

which didn't seem to help. I've attempted induction based on some other answers (like the ones found here this one), but I'm not really understanding why the inductive hypothesis is what it is claimed to be, or why the identity there has the combinatorial meaning one of the answers claim it does. If an inductive proof is possible (and perhaps it's even fairly straightforward), I'd ask for a careful explanation of what the inductive hypothesis is in this case. Thanks for any help.

Answer 1

Two tools which make quick work of this problem are

• Binomial Upper Index Negation: For all $n\in \mathbb C,k\in \mathbb N_0$, $$\binom{n}{k}=(-1)^k\binom{-n+k-1}{k}.$$

• Chu-Vandermonde Identity: For all $s,t\in \mathbb C,k\in \mathbb N_0$, $$\sum_{i=0}^k \binom{s}{i}\binom{t}{k-i}=\binom{s+t}{k}.$$

In order for these to make sense, you need to adopt the convention that $\binom{n}{k}=\frac{n(n-1)\cdots (n-k+1)}{k!}$, which allows $\binom{n}k$ to be well defined even when $n$ is complex (or an element of any ring $R$ containing the rational numbers).

Then, \begin{align} \sum_{r}\binom{n}{q-r}\binom{n-q+r}{r}(-1)^r=\sum_r \binom{n}{q-r}\binom{-n+q-1}{r}=\binom{q-1}q \end{align}

which is obviously zero.

Answer 2

A combinatorial proof isn’t hard. Letting $m=n-q$ in your rewritten version, we want to show that

$$\sum_{r=0}^{n-m}\binom{n}r\binom{n-r}m(-1)^r=0\,.\tag{1}$$

The lefthand side of $(1)$ is the number of ordered pairs $\langle A,B\rangle$ such that $A,B\subseteq[n]$, $A\cap B=\varnothing$, and $|B|=m$, where a pair is counted positively if $|A|$ is even, and negatively if $|A|$ is odd. Thus, if $[n]^m$ is the set of $m$-element subsets of $[n]$, then

$$\begin{align*} \sum_{r=0}^{n-m}\binom{n}r\binom{n-r}m(-1)^r&=\sum_{B\in[n]^m}\sum_{A\subseteq[n]\setminus B}(-1)^{|A|}\\ &=\sum_{B\in[n]^m}\sum_{r=0}^{n-m}\binom{n-m}r(-1)^r\\ &=\sum_{B\in[n]^m}(1-1)^{n-m}\\ &=\begin{cases} 1,&\text{if }m=n\\ 0,&\text{if }m<n\,. \end{cases} \end{align*}$$

And $m<n$, since you’re assuming that $q\ge 1$, so $(1)$ holds.