# Combinatorial proof involving factorials

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.

-

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

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

-
+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:

$$\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.

-