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}}}.

 

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s