If $n, k, m$ are positive integers and $k\le n$ prove that: $\sum_{r=0}^{m}\frac{k*{m\choose r}*{n\choose k}}{(k+r){m+n\choose r+k}}=1$
I did not know how to do it, I attempted some things, but they didn't work out. I hence looked at the solution stated that this is equivalent to:
$\sum_{r=0}^{m} {k+r-1\choose k-1}*{m+n-k-r\choose m-r}={m+n\choose n}$
which are both equal to the amount of subsets of {1,2,...,m+n} of size n.
Could you please explain to me why this holds true? Why the two sums are equal and why it is equal to the subtotals?
Write the summand as$$\begin{align}\frac{k\cdot m!n!(r+k)!(m+n-r-k)!}{r!(m-r)!k!(n-k)!(r+k)\cdot(m+n)!}&=\frac{m!n!(r+k-1)!(m+n-r-k)!}{r!(m-r)!(k-1)!(n-k)!(m+n)!}\\&=\frac{\binom{r+k-1}{k-1}\binom{m+n-k-r}{m-r}}{\binom{m+n}{n}}.\end{align}$$A slight correction to your terminology: the solution's points is that the number of size-$n$ subsets of $\{1,\,2,\,\cdots,\,m+n\}$ is $\binom{m+n}{n}$. Now we use a double-counting argument. Let $k+r$ denote the $k$th smallest element of the subset, so $0\le r\le m$, and the least $k-1$ elements are chosen from $\{1,\,\cdots,\,k+r-1\}$ in one of $\binom{k+r-1}{k-1}$ ways. The $n-k$ elements larger than $k+r$ are chosen from $\{k+r+1,\,\cdots,\,m+n\}$ in one of $\binom{m+n-k-r}{n-k}=\binom{m+n-k-r}{m-r}$ ways.