2
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The almost trivial generalization of ${n \choose k}$ blew my mind. Thanks for the simple and very clear answer! $\endgroup$ – flevinBombastus Feb 24 at 18:19
  • 1
    $\begingroup$ @flevinBombastus Happy to help. Let me say shed some light on why this generalization is so useful. The binomial coefficients are are the coefficients of the Taylor series $(1+x)^n$, and these generalized binomial coefficients appear as the coefficients of $(1+x)^n$ when $n$ is complex (see Newton's binomial theorem). You can prove the Chu-Vandermonde identity by looking at the coefficients of both sides of $(1+x)^{s+t}=(1+x)^s(1+x)^t$. $\endgroup$ – Mike Earnest Feb 24 at 18:23
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks for the answer. I'm a little confused about the intuition at the beginning. I'm used to thinking of ${n \choose m}$ as the number of ways one could pick $m$ things from a set of $n$ things, and I'm having a hard time squaring that with the counting explanation you gave. Particularly, I see $|B|=m$ but I don't see why we can pick $B \subseteq [n]$ so long as $A \cap B = \varnothing$ and that's equivalent to the mathematical expression. Could you elaborate on that? $\endgroup$ – flevinBombastus Feb 24 at 19:16
  • 1
    $\begingroup$ @flevinBombastus: For any given size $r$ of the set $A$ there are $\binom{n}r$ ways to choose $A$, and there are then $\binom{n-r}m$ ways to choose $B\in[n]^m$ disjoint from $A$. I’m just pointing out that we could get the same pairs by choosing $B\in[n]^m$ first and then pairing it with any subset of $[n]\setminus B$. $\endgroup$ – Brian M. Scott Feb 24 at 19:22
  • $\begingroup$ Oh, shoot, for some reason I was reading and thinking $A \cap B \neq \varnothing$ rather than $A \cap B = \varnothing$. Thanks for explaining so patiently! $\endgroup$ – flevinBombastus Feb 24 at 19:28
  • $\begingroup$ @flevinBombastus: You’re welcome! $\endgroup$ – Brian M. Scott Feb 24 at 19:28

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