TAOCP 1.2.6 Exercise 63

Exercise 63. [M30] If $l,m,n$ are integers and $n \ge 0$, prove that

$$ \sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l}\binom{s-r}{m-n-l}. $$

Verified: no
Solve time: -

Setup

We must prove that, for integers $l,m,n$ with $n \ge 0$,

$$ \sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l}\binom{s-r}{m-n-l}. $$

All sums extend over all integers $j,k$. Since the binomial coefficients vanish outside their natural ranges, only finitely many terms are nonzero.

The proof uses the addition formula (9) and the binomial theorem (13).

Solution

Define

$$ S=\sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j}. $$

Introduce the generating function

$$ F(x)=\sum_m Sx^m. $$

Substituting the definition of $S$ gives

$$ F(x) = \sum_{j,k} (-1)^{j+k} \binom{j+k}{k+l} \binom{r}{j} \binom{n}{k} \sum_m \binom{s+n-j-k}{m-j}x^m. $$

Put $t=m-j$. Then

$$ \sum_m \binom{s+n-j-k}{m-j}x^m = x^j\sum_t \binom{s+n-j-k}{t}x^t. $$

By the binomial theorem (13),

$$ \sum_t \binom{s+n-j-k}{t}x^t = (1+x)^{s+n-j-k}. $$

Therefore

$$ F(x) = \sum_{j,k} (-1)^{j+k} \binom{j+k}{k+l} \binom{r}{j} \binom{n}{k} x^j(1+x)^{s+n-j-k}. $$

Factor out $(1+x)^{s+n}$:

$$ F(x) = (1+x)^{s+n} \sum_{j,k} \binom{j+k}{k+l} \binom{r}{j} \binom{n}{k} \left(-\frac{x}{1+x}\right)^j \left(-\frac1{1+x}\right)^k. $$

Set

$$ u=-\frac{x}{1+x}, \qquad v=-\frac1{1+x}. $$

Then

$$ F(x) = (1+x)^{s+n} \sum_{j,k} \binom{j+k}{k+l} \binom{r}{j} \binom{n}{k} u^jv^k. $$

Now use the identity

$$ \binom{j+k}{k+l} = w^{k+l}^{j+k}, $$

where $[w^a]$ denotes coefficient extraction. Hence

$$ \sum_{j,k} \binom{j+k}{k+l} \binom{r}{j} \binom{n}{k} u^jv^k = [w^l] \sum_{j,k} \binom{r}{j} \binom{n}{k} (u(1+w))^j(v(1+w))^kw^{-k}. $$

Since

$$ w^{-(k+l)}=w^{-l}w^{-k}, $$

extracting the coefficient of $w^{k+l}$ is equivalent to extracting the coefficient of $w^l$ after multiplication by $w^{-k}$. Thus

$$= [w^l] \left( \sum_j \binom{r}{j}(u(1+w))^j \right) \left( \sum_k \binom{n}{k}\left(\frac{v(1+w)}{w}\right)^k \right).$$

Applying the binomial theorem (13) to both sums,

$$= [w^l] (1+u+uw)^r \left(1+\frac{v(1+w)}{w}\right)^n.$$

Substitute the values of $u$ and $v$:

$$ 1+u+uw = 1-\frac{x}{1+x}-\frac{xw}{1+x} = \frac{1-xw}{1+x}, $$

and

$$ 1+\frac{v(1+w)}{w} = 1-\frac{1+w}{w(1+x)} = \frac{xw-1}{w(1+x)}. $$

Therefore

$$ F(x) = (1+x)^{s+n} [w^l] \left(\frac{1-xw}{1+x}\right)^r \left(\frac{xw-1}{w(1+x)}\right)^n. $$

Since

$$ xw-1=-(1-xw), $$

we obtain

$$ F(x) = (-1)^n (1+x)^{s-r} [w^l] (1-xw)^{n+r}w^{-n}. $$

Now

$$ (1-xw)^{n+r} = \sum_t \binom{n+r}{t}(-xw)^t, $$

hence

$$ (1-xw)^{n+r}w^{-n} = \sum_t (-1)^t \binom{n+r}{t} x^t w^{t-n}. $$

The coefficient of $w^l$ occurs when

$$ t-n=l, \qquad t=n+l. $$

Therefore

$$ w^l^{n+r}w^{-n} = (-1)^{n+l} \binom{n+r}{n+l} x^{n+l}. $$

Substituting into $F(x)$ gives

$$ F(x) = (-1)^l \binom{n+r}{n+l} x^{n+l}(1+x)^{s-r}. $$

Applying the binomial theorem again,

$$ (1+x)^{s-r} = \sum_q \binom{s-r}{q}x^q. $$

Hence

$$ F(x) = (-1)^l \binom{n+r}{n+l} \sum_q \binom{s-r}{q} x^{q+n+l}. $$

The coefficient of $x^m$ is therefore

$$ S = (-1)^l \binom{n+r}{n+l} \binom{s-r}{m-n-l}. $$

This is the required identity.

This completes the proof.

∎

Verification

Take $l=0$. The identity becomes

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

For $r=0$, only the term $j=0$ survives, and the left side reduces to

$$ \sum_k (-1)^k \binom{n}{k} \binom{s+n-k}{m}. $$

The right side becomes

$$ \binom{n}{n}\binom{s}{m-n} = \binom{s}{m-n}. $$

Using generating functions,

$$ \sum_m \left( \sum_k (-1)^k \binom{n}{k} \binom{s+n-k}{m} \right)x^m = \sum_k (-1)^k \binom{n}{k} (1+x)^{s+n-k}, $$

which equals

$$ (1+x)^{s+n} \left(1-\frac1{1+x}\right)^n = x^n(1+x)^s. $$

The coefficient of $x^m$ is $\binom{s}{m-n}$, agreeing with the formula.

Notes

The argument is an application of coefficient extraction together with repeated use of the binomial theorem (13). The factor

$$ \binom{j+k}{k+l} $$

is handled by representing it as a coefficient of $(1+w)^{j+k}$, after which the sums over $j$ and $k$ separate completely.