## A Sum of Ratios of Binomial Coefficients

In this post we evaluate the sum $\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}}$.  Then we’ll generalize it and evaluate $\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}\binom{k}{r}}{\binom{n}{k}}$.

The key tools we need for the first sum are the trinomial revision identity, $\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}$, and the parallel summation identity, $\sum_{k=0}^m \binom{n+k}{k} = \binom{n+m+1}{m}$.  Using trinomial revision, we have

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

We can evaluate the remaining sum using parallel summation, but we need to pull a variable switch first.  Replace k with $m-k$ and then apply parallel summation to obtain

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

We thus have the identity

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

where the last step follows thanks to some algebra simplification with factorials.

To evaluate the second sum we’ll need an identity that’s like an upper-index version of Vandermonde’s convolution: $\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} = \binom{m+n+1}{r+s+1}$.  Otherwise, the derivation for the second sum proceeds just as the first one does up through the point where we replace k with $m-k$.  Continuing from there and applying the upper Vandermonde identity, we have

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

We can rewrite this and perform some more algebra simplification to get our generalization:

$\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}\binom{k}{r}}{\binom{n}{k}} = \frac{\binom{n+1}{m-r}}{\binom{n}{m}} = \frac{n+1}{m^{\underline{r}} (n+1-m)^{\underline{r+1}}}.$

This entry was posted in binomial coefficients. Bookmark the permalink.