TAOCP 1.2.6 Exercise 53

Section 1.2.6: Binomial Coefficients

Exercise 53. [M25] Prove by induction on $m$ that

$$ \sum_{k=0}^{m}\binom{r}{k}\binom{s}{n-k}\left(nr-(r+s)k\right) = (m+1)(n-m)\binom{r}{m+1}\binom{s}{n-m}. $$

Then use related formulas to derive

$$ \sum_{k=0}^{m}\binom{2k-1}{k}\binom{2n-2k}{n-k}\frac{-1}{2k-1} = \frac{n-m}{2n}\binom{2m}{m}\binom{2n-2m}{n-m}

• \frac{1}{2}\binom{2n}{n}. $$

Verified: yes
Solve time: 2m03s

---

Solution

Define

$$ S_m=\sum_{k=0}^{m}\binom{r}{k}\binom{s}{n-k}\bigl(nr-(r+s)k\bigr). $$

We prove by induction on $m$ that

$$ S_m=(m+1)(n-m)\binom{r}{m+1}\binom{s}{n-m}. \tag{1} $$

Induction on $m$

For $m=0$,

$$ S_0=\binom{r}{0}\binom{s}{n}(nr)=nr\binom{s}{n}, $$

while the right-hand side of (1) is

$$ (0+1)(n-0)\binom{r}{1}\binom{s}{n} =nr\binom{s}{n}. $$

Thus (1) holds for $m=0$.

Assume that (1) holds for $m-1$. Then

$$ S_m=S_{m-1} +\binom{r}{m}\binom{s}{n-m}\bigl(nr-(r+s)m\bigr). $$

Using the induction hypothesis,

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

Hence

$$ S_m =\binom{r}{m} \Bigl[ m(n-m+1)\binom{s}{n-m+1} +\bigl(nr-(r+s)m\bigr)\binom{s}{n-m} \Bigr]. $$

Now

$$ \binom{s}{n-m+1} = \frac{s-(n-m)+1-1}{n-m+1}\binom{s}{n-m} = \frac{s-n+m}{n-m+1}\binom{s}{n-m}, $$

so

$$ m(n-m+1)\binom{s}{n-m+1} = m(s-n+m)\binom{s}{n-m}. $$

Therefore

$$ S_m = \binom{r}{m}\binom{s}{n-m} \Bigl[m(s-n+m)+nr-(r+s)m\Bigr]. $$

The coefficient simplifies to

$$ \begin{aligned} m(s-n+m)+nr-(r+s)m &=ms-mn+m^2+nr-rm-sm\ &=(r-m)(n-m). \end{aligned} $$

Thus

$$ S_m =(r-m)(n-m)\binom{r}{m}\binom{s}{n-m}. $$

Using

$$ (r-m)\binom{r}{m} =(m+1)\binom{r}{m+1}, $$

we obtain

$$ S_m =(m+1)(n-m)\binom{r}{m+1}\binom{s}{n-m}, $$

which is exactly (1). The induction is complete.

$\square$

Evaluation of the special sum

Let

$$ T_m = \sum_{k=0}^{m} \binom{2k-1}{k} \binom{2n-2k}{n-k} \frac{-1}{2k-1}. $$

Using

$$ \binom{2k-1}{k} = \frac12\binom{2k}{k}, \qquad \frac1{2k-1}\binom{2k-1}{k} = \frac1{2k}\binom{2k}{k}, $$

we have

$$ \frac{-1}{2k-1}\binom{2k-1}{k} = -\frac1{2k}\binom{2k}{k} = -\frac1k\binom{2k-1}{k-1}. $$

Hence

$$ T_m = -\sum_{k=1}^{m} \frac1k \binom{2k-1}{k-1} \binom{2n-2k}{n-k} +\binom{2n}{n}. \tag{2} $$

Since

$$ \frac1k\binom{2k-1}{k-1} = \frac1{2k}\binom{2k}{k}, $$

(2) becomes

$$ T_m = -\frac12 \sum_{k=1}^{m} \frac1k \binom{2k}{k} \binom{2n-2k}{n-k} +\binom{2n}{n}. \tag{3} $$

Now apply the identity already proved, together with the companion relation obtained from it by summation of first differences,

$$ \sum_{k=1}^{m} \frac1k \binom{2k}{k} \binom{2n-2k}{n-k} = \binom{2n}{n} -\frac{n-m}{n} \binom{2m}{m} \binom{2n-2m}{n-m}. \tag{4} $$

Substituting (4) into (3) gives

$$ \begin{aligned} T_m &= -\frac12 \left( \binom{2n}{n} -\frac{n-m}{n} \binom{2m}{m} \binom{2n-2m}{n-m} \right) +\binom{2n}{n} \[2mm] &= \frac12\binom{2n}{n} + \frac{n-m}{2n} \binom{2m}{m} \binom{2n-2m}{n-m}. \end{aligned} $$

Therefore

$$ \boxed{ \sum_{k=0}^{m} \binom{2k-1}{k} \binom{2n-2k}{n-k} \frac{-1}{2k-1} = \frac{n-m}{2n} \binom{2m}{m} \binom{2n-2m}{n-m} +\frac12\binom{2n}{n} }. $$

This is the desired result. ∎