# Binomial probability with summation

Show that

$$\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac{n+1}{n-m+1}$$

Attempt:

It becomes:

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

Telescoping, pairing, binomial theorem don't seem to work

Possibly a combinatoric proof?

Considering the cards of numbers 1, 2, 3, 4, ... , m, .... , n on the table. We must pick k cards from the n on the table.

The probability that we pick these k cards from the first m is

$$P(k) = \frac{\binom{m}{k}}{\binom{n}{k}}$$

So summing these probabilities will give us the LHS.

Now is there a nice way of doing this probability a different way to yield the RHS?

-
Note that, for $n \ge m$, $$\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac {m!(n-m)!}{n!}\sum_{k=0}^{m} \frac{(n-k)!}{(n-m)!(m-k)!}=\cfrac 1 {\binom n m}\sum_{k=0}^{m}\binom {n-k}{n-m}$$ –  Mark Bennet May 10 '13 at 14:28
How could it be a probability, as $n+1>n-m+1$ for $m>1$? –  Alyosha Jul 25 '13 at 20:19

I computed this sum for this answer by induction on $m$:

The formula is trivially true for $m=0$. Assume it is true for $m-1\le n-1$: \begin{align} \sum_{k=0}^m\frac{\binom{\vphantom{1+}m}{k}}{\binom{\vphantom{1+}n}{k}} &=1+\sum_{k=1}^m\frac{\frac{\vphantom{1+}m}{k}\binom{m-1}{k-1}}{\frac{n}{k}\binom{n-1}{k-1}}\\ &=1+\frac{m}{n}\sum_{k=0}^{m-1}\frac{\binom{m-1}{k}}{\binom{n-1}{k}}\\[6pt] &=1+\frac{m}{n}\frac{n}{n-m+1}\\[9pt] &=\frac{n+1}{n-m+1} \end{align} Thus, it is true for all $m\le n$.

However, if we work from Mark Bennet's comment, we get \begin{align} \sum_{k=0}^m\frac{\binom{\vphantom{1+}m}{k}}{\binom{\vphantom{1+}n}{k}} &=\frac1{\binom{\vphantom{1+}n}{m}}\sum_{k=0}^m\binom{n-k}{n-m}\binom{k}{0}\\[6pt] &=\frac{\binom{n+1}{n-m+1}}{\binom{\vphantom{1+}n}{m}}\\[6pt] &=\frac{\frac{n+1}{n-m+1}\binom{\vphantom{1+}n}{n-m}}{\binom{\vphantom{1+}n}{m}}\\[6pt] &=\frac{n+1}{n-m+1} \end{align}

-
Is there a name for the identity $$\sum_{k=j}^{n-i}\binom{n-k}{i}\binom{k}{j}=\binom{n+1}{i+j+1}$$ It can be proven using the Chu-Vandermonde Identity and negative binomial coefficients, but is it still called Chu-Vandermonde? –  robjohn May 10 '13 at 16:33

If I write your sum as a hypergeometric series, it becomes $$\sum_{k=0}^{m} \frac {m! \left(n-k\right)!}{n! \left( m-k\right)!}={}_2F_1\left( \left.\begin{array}{c} -m, 1\\-n \end{array} \right| 1 \right)$$

If $m \le n$, this is a special case of the Chu-Vandermonde identity, which will give you the desired result. You may also google "Chu-Vandermonde identity" for a combinatorial proof. It may give you a clue for a combinatorial proof of your identity.

-
Would you please explain how this is the Chu-Vandermonde Identity when $m\le n$? I am not seeing it. –  robjohn May 10 '13 at 16:15
Ah, I see a related result by looking at Mark Bennet's comment. –  robjohn May 10 '13 at 16:18