# Prove that $\sum_{k=0}^{m}\frac{\binom{m}{k}}{\binom{n}{k}}=\frac{n+1}{n+1-m}$

Prove that $\sum_{k=0}^{m}\dfrac{\binom{m}{k}}{\binom{n}{k}}=\dfrac{n+1}{n+1-m}$.

We know, n > m. From the right side. we have $\dfrac{n+1}{n+1-m}=\dfrac{1}{1-\dfrac{m}{n+1}}$. since n > m. $0<\dfrac{m}{n+1}<1$. Then $\dfrac{1}{1-\dfrac{m}{n+1}}=1+\dfrac{m}{n+1}+(\dfrac{m}{n+1})^2+...$ I don't know what to do next? Did I choose the right path?

• Since the sum $1+\dfrac{m}{n+1}+\left(\dfrac{m}{n+1}\right)^2+...$ has infinite terms and the left hand side of your original equation has only finite terms, there is no hope equating the two, term by term. Do you have any other strategy? – Isomorphism Oct 18 '13 at 6:00
• If $m > n$, then the left hand side is infinite, since the denominator of the last $m - n$ terms becomes $0$. – Lucian Oct 18 '13 at 6:17

Here's a probabilistic proof.

We have $n$ balls in a bag, $m$ are white, $r=n-m$ are red. We do the following experiment: we draw a random integer $k$, uniformly distributed in $0 \dots n$, and then we pick randomly $k$ balls (without replacement). Let $W$ be the event that all balls are white (more precisely, that no ball is red).

Then $$P(W |k) = \frac{{m \choose k}}{{n \choose k}} [k\le m]$$ and $$P(W) = \sum_{k} P(W |k) P(k) =\frac{1}{n+1} \sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} \tag{1}$$

Alternatively, our experiment is equivalent to: produce a random permutation of the $n$ balls, then check if the first $k$ balls ($k$ drawn as before) are white. Which is the same as saying: place a random bar in between the $n$ balls ($n+1$ positions) and check if it falls before the first red ball. Which is the same as thinking the bar as a new additional red ball, and looking if this one is the first red ball among the total $r+1$ red balls. Then

$$P(W)=\frac{1}{r+1}=\frac{1}{n-m+1} \tag{2}$$

Equating (1) and (2) we get the desired result.

A similar alternative combinatorial way: We have $n+1$ balls, $m$ white, $r=n-m$ red, and one orange, otherwise undistinguishable. Let's $C$ count the number of ways of placing the balls in $n+1$ cells (numbered from $0$ to $n$) so that no red ball is before the orange one.

Summing over all the positions of the orange ball, we have

$$C= \sum_{k=0}^m {n-k \choose m-k} ={n \choose m}\sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} \tag{3}$$

(for last equality see Isomorphism's answer).

On the other side, we can consider the orange-red balls as a group (considering the orange distinguishable and placing it first, is the same as condiring the group undistinguishable), which gives ${n+1 \choose m}$ arrangements. Hence

$$C={n+1 \choose m} ={n \choose m} \frac{n+1}{n-m+1} \tag{4}$$

(again, for last equality see Isomorphism's answer).

Equating (3) and (4) we get the desired result.

• This is a great proof! In the final displayed equation, $n-1$ should be $n+1$, no? It's just a typo, not a mathematical error. – Steve Kass Oct 19 '13 at 1:59
• Typo fixed, thanks! – leonbloy Oct 19 '13 at 2:13

You can solve your problem by following these steps:

1) First show that $$\dfrac{\binom{m}{k}}{\binom{n}{k}} = \dfrac{\binom{n-k}{m-k}}{\binom{n}{m}}.$$

2) Now show that $$\binom{n}{m}\cdot\dfrac{n+1}{n+1-m} = \binom{n+1}{m}.$$

3) Use steps 1 and 2 to prove that the equation you require is equivalent to proving

$$\sum_{k=0}^m\binom{n-k}{m-k} = \binom{n+1}{m}.$$

4)Now prove the relation: $$\sum_{k=0}^m\binom{n-k}{m-k} = \binom{n+1}{m}.$$

4a) You can prove this relation in various ways. One of them is to write $\binom{n-m}{0}$ as $\binom{n-m+1}{0}$ and then repeatedly use the relation $\binom{x}{r}+\binom{x}{r-1} = \binom{x+1}{r}$. Another method is induction.

Best of luck!

Using the Heaviside Method for Partial Fractions, we get \begin{align} \sum_{k=0}^m\frac{\binom{m}{k}}{\binom{n}{k}} &=1+\sum_{k=1}^m\frac{m(m-1)(m-2)\dots(m-k+1)}{n(n-1)(n-2)\dots(n-k+1)}\tag{1}\\ &=1+m\sum_{k=1}^m\sum_{j=0}^{k-1}\frac{(-1)^{k-j-1}\binom{m-1}{k-1}\binom{k-1}{j}}{n-j}\tag{2}\\ &=1+m\sum_{k=1}^m\sum_{j=0}^{k-1}\frac{(-1)^{k-j-1}\binom{m-1}{j}\binom{m-j-1}{k-j-1}}{n-j}\tag{3}\\ &=1+m\sum_{j=0}^{m-1}\sum_{k=j+1}^m\frac{(-1)^{k-j-1}\binom{m-1}{j}\binom{m-j-1}{k-j-1}}{n-j}\tag{4}\\[6pt] &=1+\frac{m}{n-m+1}\tag{5}\\[6pt] &=\frac{n+1}{n-m+1}\tag{6} \end{align} Explanation:

$(1)$: break out the $k=0$ term and expand numerator and denominator
$(2)$: apply the Heaviside Method to the fraction in the sum
$(3)$: $\binom{m-1}{k-1}\binom{k-1}{j}=\binom{m-1}{j}\binom{m-j-1}{k-j-1}$
$(4)$: switch the order of summation
$(5)$: $\sum\limits_{k=j+1}^m(-1)^{k-j-1}\binom{m-j-1}{k-j-1}=0^{m-j-1}=\big[j=m-1\big]$
$(6)$: addition