Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 9 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|cite|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

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


We are done.

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

First rearrange the identity:


Then note that


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


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

Your Answer


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.