Looking for a proof of a weird Combinatoric identity I came across

111 Views Asked by At

Earlier today I came up with a very complicated "proof" of the probability multiplication rule for two independent events. I used the quotation marks because I ended up obtaining a very complicated formula for the wanted probability, and only verified that it gave the right values for different parameters by using desmos. But, I don't know how to simplify the formula into the more basic form. In short, I want to show that

$$ \sum_{i=1}^R \frac{i}{N}\frac{\frac{N!}{i! (R-i)! (B-i)!(N+i-R-B)!}}{\binom{N}{R} \binom{N}{B}}= \frac{RB}{N^2} $$

Where $R\le B$, And $R+B\le N$

does anyone have any idea of how to do this?

2

There are 2 best solutions below

1
On

LHS can be simplified to: $$\sum_{i=1}^R\frac{i}N\frac{\binom{R}i\binom{N-R}{B-i}}{\binom{N}B}$$

Then to be explained is the equality:$$\sum_{i=1}^R\frac{i\binom{R}i\binom{N-R}{B-i}}{\binom{N}B}=\frac{RB}N$$

The LHS of this equality can be recognized as the expectation of the number of red balls that appear if $B$ balls are taken randomly and without replacement from an urn that contains exactly $N$ balls of which exactly $R$ are red balls.

Note that the LHS is $\sum_{i=1}^Bip_i$ where $p_i$ denotes the probability that $i$ red balls are drawn.

This expectation can be found on a more elegant way using linearity of expectation and symmetry.

For $i=1,\dots,B$ let $X_i$ take value $1$ if at the $i$-th draw a red ball is chosen and let $X_i$ take value $0$ otherwise.

Then to be found is: $$\mathbb E(X_1+\dots+X_B)=B\times\mathbb EX_1=B\times\frac{R}{N}=\frac{RB}{N}$$

So this tells us that the equality is a true statement.


Maybe this does not answer your question and you are after some unraveling of the LHS that ends up in the RHS. In that case I feel a too strong reluctance to think about any answer.

0
On

$$\begin {array}{} \sum\limits_{i=1}^R \frac{i}{N}\frac{\frac{N!}{i! (R-i)! (B-i)!(N+i-R-B)!}}{\binom{N}{R} \binom{N}{B}} &=\frac{1}{N\binom{N}{B}}\sum\limits_{i=1}^R i\binom{R}i\binom{N-R}{B-i}\\ &=\frac{R}{N\binom{N}{B}}\sum\limits_{i=1}^R\binom{R-1}{i-1}\binom{N-R}{B-i}\\ &=\frac{R}{N\binom{N}{B}}\sum\limits_{i=0}^{R-1}\binom{R-1}{i}\binom{N-R}{B-1-i}\\ &\stackrel{V.I.}{=}\frac{R}{N\binom{N}{B}}\binom{N-1}{B-1}=\frac{RB}{N^2}, \end {array} $$ where $V.I.$ means Vandermonde's identity.