2
$\begingroup$

Can anyone suggest how to prove the following (for $k \le n$):

$$\sum \limits_{s=0}^N \frac{\binom{n}{k} \binom{N-n}{s-k} }{\binom{N}{s}} = \frac{N+1}{n+1}$$

I am assuming it to be true, and possibly well known.

$\endgroup$
7
  • $\begingroup$ Expand into factorials and recombine them into $\binom{s}{k}$ and $\binom{N-s}{n-k}$. $\endgroup$ Feb 9, 2016 at 3:02
  • $\begingroup$ What's the context? How did you know what the answer should be? $\endgroup$
    – David Roberts
    Feb 9, 2016 at 3:46
  • 1
    $\begingroup$ Thank you Max! Simply, $\sum \limits_{s=0}^N \frac{\binom{n}{k} \binom{N-n}{s-k} }{\binom{N}{s}} = \sum \limits_{s=0}^N \frac{\binom{s}{k} \binom{N-s}{n-k}}{\binom{N}{n}} = \frac{N+1}{n+1}$ The last is evident from a basic counting argument $\endgroup$ Feb 9, 2016 at 5:03
  • $\begingroup$ @David The context is the probability of observing a total of k 'items' after looking at n 'locations', in a world with a total of s items uniformly placed in N locations. $\endgroup$ Feb 9, 2016 at 5:28
  • 2
    $\begingroup$ @DavidRoberts the context is a very simple example which demonstrates Bayesian principles. This came up when computing the marginal. $\endgroup$ Feb 9, 2016 at 8:52

0