TAOCP 1.2.6 Exercise 30

Example 3 in Section 1.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 30. [M24] Show that there is a better way to solve Example 3 than the way used in the text, by manipulating the sum so that Eq. (26) applies.

Verified: no
Solve time: -

Solution

Example 3 in Section 1.2.6 considers the sum

$$ S = \sum_{k=0}^{n} \binom{r+k}{k} \binom{s-k}{n-k}, $$

and in the text, it is evaluated by direct manipulation. We are asked to show a better method by transforming the sum so that Eq. (26) from the preceding exercises applies. Equation (26) states

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

The key idea is to rewrite the second factor $\binom{s-k}{n-k}$ in the original sum in a form that matches the pattern of Eq. (26). By the symmetry property (Eq. (6)),

$$ \binom{s-k}{n-k} = \binom{s-k}{(s-k)-(s-n)} = \binom{s-k}{s-n-(k-(0))} = \binom{s-n}{n-k} \binom{\text{?}}{\text{?}}, $$

but a simpler route is to apply the "moving in and out of parentheses" formula (Eq. (7)) recursively. Specifically, we have

$$ \binom{s-k}{n-k} = \frac{s-n+1}{s-k-n+k+1}\binom{s-1-k}{n-1-k}, $$

which appears complicated. A more direct method is to shift the summation index to absorb the $-k$ term. Let $j = n-k$. Then $k = n-j$, and as $k$ ranges from $0$ to $n$, $j$ ranges from $n$ to $0$. Rewriting $S$ in terms of $j$:

$$ \begin{aligned} S &= \sum_{k=0}^{n} \binom{r+k}{k} \binom{s-k}{n-k} \ &= \sum_{j=0}^{n} \binom{r+n-j}{n-j} \binom{s-(n-j)}{j} \ &= \sum_{j=0}^{n} \binom{r+n-j}{n-j} \binom{s-n+j}{j}. \end{aligned} $$

Next, we apply the symmetry property (Eq. (6)) to the first factor:

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

Substituting this into the sum, we obtain

$$ S = \sum_{j=0}^{n} \binom{r+n-j}{r} \binom{s-n+j}{j}. $$

This sum now matches exactly the form of Eq. (26), which states that

$$ \sum_{k=0}^{n} \binom{R+k}{k} \binom{S}{n-k} = \binom{R+S+n+1}{n}. $$

Comparing, we set $R = s-n$, $S = r$, and $k = j$. Then by Eq. (26),

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

Hence, the sum $S$ evaluates to

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

This approach avoids the step-by-step expansion used in the text and directly applies the previously established identity by an appropriate change of summation index and use of symmetry. This completes the proof.

∎