Closed form for a series of combinations Let $M$, $N$, and $n$ be three integer numbers such that $n$ is smaller than both $M$ and $N$ ($n < M$ and $n < N$). I would like to know if $\sum_{i = 0}^{n - 1}{N-1 \choose i} {M \choose n - 1 - i}$ has a closed-form solution.
Here is why I am interested in this sum: Assume we have $M$ white and $N$ black balls in an urn. If only one of the black balls has a dot on it and we randomly select $n$ balls from the urn, I need to calculate the probability that the dotted black ball is among the selected ones.
$\Pr(\text{dotted black ball is selected}) = \frac{\sum_{i = 0}^{n - 1} \text{(dotted selected)} \times \text{($i$ of the non-dotted blacks selected)} \times \text{($n-1-i$ of the white selected)}}{{\text{selecting $n$ out of $M+N$}}} =\frac{\sum_{i = 0}^{n - 1} 1 \times {N-1 \choose i} \times {M \choose n - 1 - i}}{{M + N\choose n}}$
Actually, I need to study the sensitivity of this probability to $M$ when both $M$ and $N$ are large. For example, when $N = 100,000$, I want to know how the probability changes by $M$ if it varies between $20,000$ and $50,000$, given $n = 10,000$. That is why I need to be able to have a closed-form for the numerator to be able to calculate the numerical value of the probability.
 A: This is just a special case of Vandermonde's identity:
$$\sum_{i = 0}^{n - 1}{N-1 \choose i} {M \choose n - 1 - i} = {M+N-1 \choose n-1}$$
and the result follows immediately if you think that once chosen the spotted black ball you remain with ${M+N-1 \choose n-1}$ choices for the other balls.
And note that the probability is equal to:
$$\frac{n}{M+N}$$
because drawing one ball at a time, the probability of finding the spotted black one within attempt $k$ is:
$$P_k=P_{k-1}+(1-P_{k-1})\frac{1}{M+N-k+1}=\frac{k}{M+N}$$
and:
$$P_1=\frac{1}{M+N}$$.
A: Your formula is more complicated than it needs to be.  If you have $\ B\ $ balls of which exactly one is marked with a dot, and you choose $\ n\ $ of them at random, then the probability that the dotted ball will be among the $\ n\ $ chosen is $\ \displaystyle\frac{n}{B}\ $. In your case $\ B=M+N\ $, so the probability that the dotted black ball is chosen is $\ \displaystyle\frac{n}{M+N}\ $ for any $\ n=1,2,\dots,\ $$M+N\ $.
This tells you that you must have
\begin{align}
\sum_{i=0}^{n}{N-1\choose i}{M\choose n-i}&=
\frac{n+1}{N+M}{N+M\choose n+1}\\
&={M+N-1\choose n}\ ,
\end{align}
for $\ n=0,1,\dots,\min(M-1,N-1)\ $, and, indeed, this identity is not difficult to prove using generating  functions.
