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

I tried thinking of what the LHS summand could possibly be (permutation, combination), but I can't come up with anything; nor was I able to come up with a combinatorial proof.

share|improve this question
add comment

3 Answers

up vote 8 down vote accepted

$$\dfrac{m!}{n!} \sum_{k=0}^m \dfrac{(n-k)!}{(m-k)!} = \dfrac{m!(n-m)!}{n!} \left(\sum_{k=0}^m \dfrac{(n-k)!}{(m-k)!(n-m)!} \right)$$ We get \begin{align} \sum_{k=0}^m \dfrac{(n-k)!}{(m-k)!(n-m)!} & = \sum_{k=0}^m \dbinom{n-k}{n-m}\\ & = \sum_{k=n-m}^n \dbinom{k}{n-m}\\ & = \dbinom{n+1}{n-m+1}\,\,\,\,\,\,\,\,\,\, (\spadesuit)\\ & = \dfrac{(n+1)!}{(n-m+1)! m!} \end{align} where $\spadesuit$ is obtained from here.

Hence, putting these two together, we get that $$\dfrac{m!}{n!} \sum_{k=0}^m \dfrac{(n-k)!}{(m-k)!} = \dfrac{m!(n-m)!}{n!} \dfrac{(n+1)!}{(n-m+1)! m!} = \dfrac{n+1}{n-m+1}$$

share|improve this answer
    
Would it have been possible to use the identity if you hadn't changed the index of $k$? I'm not sure I would be able to spot something so subtle. –  AlanH Feb 9 '13 at 21:17
    
@AlanH If you expand out the summation, you will soon realize/recognize that this is the same as other. At Least this was the way I figured it out. –  user17762 Feb 9 '13 at 21:32
add comment

Lets consider a bag has $n+1$ balls out of which $m$ are white and $n-m+1$ are black.

Let $X$ be a Random variable counting the no. of balls to be taken out of the box in order to end up with a black ball.

Clarly X takes value in the set $1,2,....,m+1 $ .

$P(X=1)=\frac{n-m+1}{n+1}$

$P(X=2)=\frac{m}{n+1}\times \frac{n-m+1}{n}$

$P(X=3)=\frac{m}{n+1} \times \frac{m-1}{n}\times \frac{n-m+1}{n-1}$

In this way $P(X=k)=\frac{m}{n+1}\times \frac{m-1}{n}.... \times \frac{m-k+2}{n-k+3}\times \frac{n-m+1}{n-k+2}=\frac{n-m+1}{n+1}\times \frac{m!(n-(k-1))!}{n!(m-(k-1))!}$

As all the probabilities must add upto $1$

We have $\displaystyle\sum_{k=1}^{m+1}P(X=k)=1$

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

$\Rightarrow\displaystyle\sum_{l=0}^{m}\frac{n-m+1}{n+1}\times \frac{m!(n-l)!}{n!(m-l)!}=1$

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

We are done.

share|improve this answer
3  
+1: Quite nice! –  Mike Spivey Feb 9 '13 at 6:29
    
Thanks @MikeSpivey.... –  Abhra Abir Kundu Feb 9 '13 at 6:30
    
As an aside, "@MikeSpivey..." doesn't work (see the explanation). You have to use something like @MikeSpivey. –  Mark S. Feb 9 '13 at 15:05
add comment

First rearrange the identity:

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

Then note that

$$\frac{(n-k)!}{(m-k)!}=(n-k)^{\underline{n-m}}\;,$$

where $x^{\underline n}$ is the falling factorial, so that the identity can be written

$$\sum_{k=0}^m(n-k)^{\underline{n-m}}=\binom{n+1}m(n-m)!\;.\tag{1}$$

The term $(n-k)^{\underline{n-m}}$ is the number of ways to choose and permute $n-m$ elements of $[n-k]$, where $0\le k\le m$. Alternatively, it’s the number of ways to choose a set of $n-m+1$ elements of $[n+1]$ whose largest element is $n-k+1$ and permute the other $n-m$ elements of the set. Thus, the lefthand side of $(1)$ counts the ways to choose $n-m+1$ elements of $[n+1]$ and permute the $n-m$ smallest of the chosen elements.

On the other hand, there are $\dbinom{n+1}{n-m+1}=\dbinom{n+1}m$ ways to choose $n-m+1$ elements of $[n+1]$, and there are then $(n-m)!$ ways to permute the $m-n$ smallest of the chosen elements, so the righthand side of $(1)$ counts the same thing, and the identity is established.

share|improve this answer
add comment

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.