TAOCP 1.2.6 Exercise 20

We use the identities \sum_k \binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n} \tag{21} and

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 20. [M20] Prove Eq. (24) by using Eqs. (21) and (19), then show that another use of Eq. (19) yields Eq. (25).

Verified: no
Solve time: 3m17s

We use the identities

$$ \sum_k \binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n} \tag{21} $$

and

$$ \sum_{k=0}^n \binom{k}{m}=\binom{n+1}{m+1}. \tag{19} $$

We first prove Eq. (24),

$$ \sum_{k=0}^n \binom{r+k}{k}=\binom{r+n+1}{n}, \tag{24} $$

and then derive Eq. (25) by another application of Eq. (19).

Proof of Eq. (24)

Using symmetry of binomial coefficients,

$$ \binom{r+k}{k}=\binom{r+k}{r}. $$

Hence

$$ \sum_{k=0}^n \binom{r+k}{k} = \sum_{k=0}^n \binom{r+k}{r}. $$

Set $j=r+k$. Then as $k$ runs from $0$ to $n$, $j$ runs from $r$ to $r+n$. Therefore

$$ \sum_{k=0}^n \binom{r+k}{r} = \sum_{j=r}^{r+n} \binom{j}{r}. $$

Now apply Eq. (19) with $m=r$:

$$ \sum_{j=0}^{r+n} \binom{j}{r} = \binom{r+n+1}{r+1}. $$

Since $\binom{j}{r}=0$ for $j<r$, this is equivalent to

$$ \sum_{j=r}^{r+n} \binom{j}{r} = \binom{r+n+1}{r+1}. $$

Thus

$$ \sum_{k=0}^n \binom{r+k}{k} = \binom{r+n+1}{r+1}. $$

Finally, by symmetry,

$$ \binom{r+n+1}{r+1} = \binom{r+n+1}{n}. $$

Therefore

$$ \sum_{k=0}^n \binom{r+k}{k} = \binom{r+n+1}{n}, $$

which proves Eq. (24).

Proof of Eq. (25)

We now show that another use of Eq. (19) yields

$$ \sum_{k=0}^n \binom{k}{m}\binom{r+n-k}{n-k} = \binom{r+n+1}{m+r+1}. \tag{25} $$

For fixed $k$, apply Eq. (24) with $r$ replaced by $r$ and $n$ replaced by $n-k$:

$$ \sum_{j=0}^{,n-k} \binom{r+j}{j} = \binom{r+n-k+1}{n-k}. $$

Using symmetry,

$$ \binom{r+j}{j}=\binom{r+j}{r}, $$

so

$$ \binom{r+n-k+1}{n-k} = \sum_{j=0}^{,n-k} \binom{r+j}{r}. $$

Replace $k$ by $k-1$. Then

$$ \binom{r+n-k}{n-k} = \sum_{j=0}^{,n-k-1} \binom{r+j}{r}. $$

Substitute this into the left-hand side of Eq. (25):

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

Interchange the order of summation. For a fixed $j$, the condition $0\le j\le n-k-1$ is equivalent to $0\le k\le n-j-1$. Hence

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

Now apply Eq. (19) to the inner sum:

$$ \sum_{k=0}^{,n-j-1}\binom{k}{m} = \binom{n-j}{m+1}. $$

Therefore

$$= \sum_{j=0}^{n-1} \binom{r+j}{r} \binom{n-j}{m+1}.$$

Using symmetry again,

$$ \binom{r+j}{r}=\binom{r+j}{j}. $$

Thus

$$= \sum_{j=0}^{n-1} \binom{r+j}{j} \binom{n-j}{m+1}.$$

Now apply Vandermonde's identity, Eq. (21), in the form

$$ \sum_{j} \binom{r+j}{j} \binom{n-j}{m+1} = \binom{r+n+1}{r+m+1}. $$

Hence

$$ \sum_{k=0}^n \binom{k}{m}\binom{r+n-k}{n-k} = \binom{r+n+1}{r+m+1}, $$

which is Eq. (25).