Wanted: Insight into formula involving binomial coefficients

Question

There is the formula $$\sum_i (-1)^i\binom{a}{k+i}\binom{l+i}{b} = (-1)^{a+k} \binom{l-k}{b-a}.$$ Only finitely many summands are non-zero (those for $i\in\{b-l,\ldots,a-k\}$), so the sum is finite.

The formula can be shown by induction. However, this does not give any further insight. So I'm looking for another proof giving a better idea why this formula is true, like deducing it from better known identities, giving a bijection between two finite sets etc.

Answer 1

Let's do a variable switch, with $n = l -k$, $m = b-a$, $j = k+i$. Then the formula to be proved is $$\sum_j (-1)^{j-k} \binom{a}{j} \binom{n+j}{m+a} = (-1)^{a+k} \binom{n}{m},$$ or $$\sum_j (-1)^j \binom{a}{j} \binom{n+j}{m+a} = (-1)^a \binom{n}{m}.$$

Now, suppose we have $a$ labeled, uncolored balls, and $n$ labeled, blue balls. Color some number of those $a$ balls red. Then let's dot $m+a$ of the colored (red and blue) balls. Define the parity of the resulting state of balls as $+1$ if there are an even number of red balls and $-1$ if there are an odd number of red balls. The left-hand side then counts the resulting signed sum over all configurations of colored and uncolored, dotted and undotted balls, where the sum conditions on the number $j$ of red balls.

Define a sign-reversing involution in the following manner: Take the highest-labeled, undotted ball that is uncolored or red and swap it to red or uncolored, respectively. This changes the parity of the configuration, and so the sum over all of the configurations for which the involution can be applied is $0$. The value of the sum, then, must be the number (including the parity) of configurations for which the involution cannot be applied. The only configurations for which the involution cannot be applied are those for which all the uncolored or red balls are dotted. So all $a$ of the uncolored balls must have been colored red, and all $a$ of those red balls must have been dotted. Thus exactly $m$ of the $n$ blue balls must have been dotted. The number of these configurations is therefore $\binom{n}{m}$, and the parity is $(-1)^a$, as there are $a$ red balls in this configuration.

Therefore, $$\sum_j (-1)^j \binom{a}{j} \binom{n+j}{m+a} = (-1)^a \binom{n}{m}.$$

Answer 2

This is (with a change of variable names) equation (5.24) in Concrete Mathematics, which stipulates that it is valid for $a\in\mathbf N$, $k,b\in \mathbf Z$ and $l\in\mathbf C$. Since the summation is over all integers, taking a new summation variable equal to $k+i$ reduces the equation to its special case $k=0$, so one may assume that without loss of generality. Apart from the combinatorial argument given by Mike Spivey, there is also a fairly transparent but merely algebraic explanation for this formula.

If $f$ is a numeric function defined on $\mathbf Z$, $\mathbf R$ or $\mathbf C$, the forward (finite) difference $\Delta f$ is the function $x\mapsto f(x+1)-f(x)$. There are two relations of $\Delta$ with binomial coefficients:

1. $\Delta(x\mapsto\binom xn)=(x\mapsto \binom x{n-1})$ for all $n\in\mathbf Z$ (with binomial coefficients defined to be $0$ if the lower index is a negative integer, and otherwise by $\binom xn=\frac{x(x-1)\ldots(x-n+1)}{n!}$). This is immediate from Pascal's recurrence $\binom{x+1}n=\binom x{n-1}+\binom xn$ (which is valid for arbitrary $x$).

2. The iterates of $\Delta$ are given by $(\Delta^k)(f)=(x\mapsto\sum_{i=0}^k(-1)^{k-i}\binom kif(x+i))$. This is obtained by writing $\Delta=S-I$ where $S:f\mapsto(x\mapsto f(x+1))$ is the shift operator and $I$ the identity operator, and applying the binomial formula (valid because $I$ and $S$ commute).

Now with the formula of 2., the function $x\mapsto \sum_i (-1)^i\binom ai \binom{x+i}b$ can be interpreted as the $a$-fold finite difference $(-\Delta)^a(x\mapsto\binom xb)$, and iterating the formula of 1. shows that this gives the function $x\mapsto(-1)^a\binom x{a-b}$. Now taking the values of these two identical functions at $x=l$ gives $$ \sum_i (-1)^i\binom ai \binom{l+i}b = (-1)^a\binom l{a-b} $$ as desired.

This proof gives exactly the generality claimed in Concrete Mathematics, i.e., we needed to assume $a\in\mathbf N$ and $b\in\mathbf Z$, but $l$ can be anything (in fact we could take it to be an indeterminate).