LEMMA 0.1   Let j, k and h be positive integers such that $1 \leq j \le k \leq h$. Then

$$\sum_{i=k}^h (-1)^{h-i} \binom{h}{i} \prod_{m=1}^{j-1}(i-k+m) = (-1)^{h-k}(j-1)!\binom{h-j}{k-j}$$ (1)

where, in the j=1 case, $\prod_{m=1}^{j-1}(i-k+m):= 1$.

Proof. We prove (1) using a generating-function approach. We begin by dividing both sides of (1) by (j-1)! and then rewriting the resulting left-hand side as

$$\sum_{i=k}^h (-1)^{h-i} \binom{h}{i} \binom{j+i-k-1}{i-k},$$

which, upon re-indexing, becomes

$$\sum_{s=0}^{h-k} (-1)^{h-s-k} \binom{h}{s+k} \binom{j-1+s}{s}.$$

Replacing the binomial coefficient of right-hand side of (1) with the equivalent $\binom{h-j}{h-k}$, and multiplying both sides by (-1)^2k-h-j, we now prove (1) by establishing that

$$\sum_{s=0}^{h-k} (-1)^{k-j-s} \binom{h}{s+k} \binom{j-1+s}{s} = (-1)^{k-j}\binom{h-j}{h-k}.$$ (2)

The right-hand side (2) is simply the coefficient of x^h-k in the polynomial (x-1)^h-j. This must be true of the left-hand side as well. Expressing (x-1)^h-j first as a rational function, and then as a series, we have

$$\begin{eqnarray*}(x-1)^{h-j}= \frac{(x-1)^h}{(x-1)^j} &=& (-1)^j (x-1)^h \frac{1... ...}\binom{h}{r}x^r \right) \sum_{s=0}^{\infty}\binom{j+s-1}{s}x^s. \end{eqnarray*}$$

Thus, the coefficient of x^h-k can be written as

$$(-1)^j \sum_{r+s=h-k}(-1)^{h-r}\binom{h}{r}\binom{j+s-1}{s}.$$

Since r=h-k-s, we obtain, after simplifying, that the coefficient of x^h-k can be written as

$$\sum_{s=0}^{h-k}(-1)^{k+j+s}\binom{h}{h-k-s}\binom{j+s-1}{s}.$$ (3)

But, noticing that (-1)^k+j+s=(-1)^k-j-s and that $\binom{h}{h-k-s}=\binom{h}{s+k}$, we find that (3) can be rewritten as

$$\sum_{s=0}^{h-k} (-1)^{k-j-s} \binom{h}{s+k} \binom{j-1+s}{s},$$

which is the left hand side of (2). Thus both sides of (2) give the coefficient of x^h-k in (x-1)^h-j. height7pt width7pt depth0pt