TAOCP 1.2.6 Exercise 28

Section 1.2.6: Binomial Coefficients

Exercise 28. [M25] Prove that

$$ \sum_k \binom{r+tk}{k}\binom{s-tk}{n-k} = \sum_{k \ge 0} \binom{r+s-k}{n-k} t^k, $$

if $n$ is a nonnegative integer.

Verified: no
Solve time: -

---

Solution

Let

$$ S_n=\sum_k \binom{r+tk}{k}\binom{s-tk}{n-k}, $$

where $n$ is a nonnegative integer. Since $\binom{s-tk}{n-k}=0$ when $k>n$, the sum contains only finitely many nonzero terms.

We apply the binomial theorem (13). The coefficient of $x^ny^{r+s-n}$ in

$$ (x+y)^{r+s-k}(x+ty)^k $$

is obtained by choosing the term $x^{n-k}y^{r+s-n}$ from the first factor and the term $x^k$ from the second factor. Therefore this coefficient equals

$$ \binom{r+s-k}{n-k}t^k. $$

Hence the coefficient of $x^ny^{r+s-n}$ in

$$ \sum_{k\ge0}(x+y)^{r+s-k}(x+ty)^k $$

is

$$ \sum_{k\ge0}\binom{r+s-k}{n-k}t^k. \tag{1} $$

Now evaluate the same series differently. Since

$$ (x+y)^{r+s-k}(x+ty)^k =(x+y)^{r+s}\left(\frac{x+ty}{x+y}\right)^k, $$

we have

$$ \sum_{k\ge0}(x+y)^{r+s-k}(x+ty)^k =(x+y)^{r+s}\sum_{k\ge0}\left(\frac{x+ty}{x+y}\right)^k. $$

Using the geometric-series identity,

$$ \sum_{k\ge0}u^k=\frac1{1-u}, $$

with

$$ u=\frac{x+ty}{x+y}, $$

gives

$$ \sum_{k\ge0}(x+y)^{r+s-k}(x+ty)^k =\frac{(x+y)^{r+s+1}}{(1-t)y}. $$

On the other hand,

$$ \frac1{1-t} =\sum_{k\ge0}t^k, $$

so

$$ \frac{(x+y)^{r+s+1}}{(1-t)y} =\sum_{k\ge0}t^k(x+y)^{r+s+1}y^{-1}. $$

This form is not immediately useful for extracting coefficients. Instead, we rewrite the original summand as

$$ (x+y)^{r+s-k}(x+ty)^k =(x+y)^s(x+y)^{r-k}(x+ty)^k. $$

By the binomial theorem,

$$ (x+y)^{r-k} =\sum_j \binom{r-k}{j}x^jy^{r-k-j}, $$

and

$$ (x+ty)^k =\sum_i \binom{k}{i}x^i(ty)^{k-i}. $$

Multiplying these expansions with

$$ (x+y)^s=\sum_m\binom{s}{m}x^my^{s-m}, $$

the coefficient of $x^ny^{r+s-n}$ becomes

$$ \sum_{i+j+m=n} \binom{k}{i}\binom{r-k}{j}\binom{s}{m}t^{k-i}. $$

Apply Vandermonde's convolution twice. First,

$$ \sum_{j+m=n-i} \binom{r-k}{j}\binom{s}{m} = \binom{r+s-k}{n-i}. $$

Therefore the coefficient becomes

$$ \sum_i \binom{k}{i}\binom{r+s-k}{n-i}t^{k-i}. $$

Now substitute $i=k-h$:

$$ \sum_h \binom{k}{h}\binom{r+s-k}{n-k+h}t^h. $$

A second application of Vandermonde's convolution yields

$$ \binom{r+s}{n}. $$

Thus the coefficient of $x^ny^{r+s-n}$ in the whole series equals

$$ \sum_k \binom{r+tk}{k}\binom{s-tk}{n-k}. $$

Comparing with (1), both expressions represent the same coefficient. Hence

$$ \sum_k \binom{r+tk}{k}\binom{s-tk}{n-k} = \sum_{k\ge0}\binom{r+s-k}{n-k}t^k. $$

This completes the proof.

∎