Prove the binomial coefficient equation

Question

Prove the equation. I'm not sure where to begin $$ \sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} = \frac{n+1}{n+1-m} . $$

Answer 1

We must have $n\ge m$, since otherwise the denominator on the left-hand side would vanish. We can extend the sum to $n$, since the added terms are $0$; so we want to show

$$ \frac1{n+1}\sum_{k=0}^n\frac{\binom mk}{\binom nk}=\frac1{n+1-m}\;. $$

Consider an urn with $n$ marbles, $m$ of which are red. Uniformly randomly choose a number $k\in[0,n]$ of marbles to draw. The left-hand side gives the probability of drawing only red marbles. Now add a marker marble, uniformly randomly choose a linear arrangement of the $n+1$ marbles and regard the marbles to the left of the marker marble as drawn. The two experiments are equivalent. In this second version, all the drawn marbles are red iff the marker marble is to the left of all $n-m$ non-red marbles, with probability $1/(n+1-m)$.

Answer 2

$$\begin{eqnarray*}\sum_{k=0}^{m}\frac{\binom{m}{k}}{\binom{n}{k}}&=&\frac {1}{n!}\sum_{k=0}^{m}\binom{m}{k}B(k+1,n-k+1)\cdot\Gamma(n+2)\\&=&(n+1)\sum_{k=0}^{m}\binom{m}{k}\int_{0}^{1}x^k(1-x)^{n-k}\,dx\\&=&(n+1)\int_{0}^{1}(1-x)^n\left(\frac{x}{1-x}+1\right)^m\,dx\\ &=& (m+1)\int_{0}^{1}(1-x)^{n-m}\,dx=\color{red}{\frac{n+1}{n+1-m}}.\end{eqnarray*}$$