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

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!

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.

Partial Fractions

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

Hockey-Stick Identity $$ \begin{align} \sum_{k=0}^m\frac{\binom{m}{k}}{\binom{n}{k}} &=\sum_{k=0}^m\frac{\frac{m!}{(m-k)!}}{\frac{n!}{(n-k)!}}\tag7\\ &=\frac{m!(n-m)!}{n!}\sum_{k=0}^m\frac{(n-k)!}{(m-k)!(n-m)!}\tag8\\ &=\frac1{\binom{n}{m}}\sum_{k=0}^m\binom{n-k}{n-m}\tag9\\ &=\frac1{\binom{n}{m}}\binom{n+1}{n-m+1}\tag{10}\\[3pt] &=\frac{n+1}{n-m+1}\tag{11} \end{align} $$ Explanation:
$\phantom{1}(7)$: expand the binomial coefficients as factorials and cancel
$\phantom{1}(8)$: shuffle factors and throw in $\frac{(n-m)!}{(n-m)!}$
$\phantom{1}(9)$: recognize binomial coefficients
$(10)$: Hockey-stick identity
$(11)$: simplify