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

 \begin{displaymath}
\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}
\end{displaymath} (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

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

which, upon re-indexing, becomes

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

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

 \begin{displaymath}
\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}.
\end{displaymath} (2)

The right-hand side (2) is simply the coefficient of xh-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 xh-k can be written as

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

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

 \begin{displaymath}
\sum_{s=0}^{h-k}(-1)^{k+j+s}\binom{h}{h-k-s}\binom{j+s-1}{s}.
\end{displaymath} (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

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

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




 

Michael Prophet
1999-09-06