Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.