# Non-probabilistic proofs of a binomial coefficient identity from a probability question

Combining the answers given by me and Ralth to the probability question at Probability Question, we get the following identity: $$\sum\limits_{k = m}^n {{n \choose k}p^k (1 - p)^{n - k} {k \choose m} p_j^m (1 - p_j )^{k - m} } = {n \choose m} (p p_j)^m (1 - p p_j)^{n-m},$$ where $m \geq 0$ and $n \geq m$ are arbitrary integers, and $p$ and $p_j$ are arbitrary probabilities (in Ralth's notation $m$ is $k$, $p$ is $p_s$, and $p_j$ is $p_h$). Can you prove this identity directly (i.e., in a non-probabilistic setting)? Whether you'll find this identity interesting or not, at least Ralth's answer may now gain its due recognition.

-

We can prove this using the Multinomial Theorem.

We have, using the Multinomial Theorem, that

$$\displaystyle (a+b+c)^n = \sum_{m=0}^{n} \sum_{k=m}^{n} {n \choose k}{k \choose m} a^m b^{k-m} c^{n-k}$$

Set $\displaystyle a = pp_j x$, $b = p(1-p_j)$, $c = 1-p$.

We get

$$\displaystyle (pp_jx + p(1-p_j) + 1-p )^n = \sum_{m=0}^{n} \sum_{k=m}^{n} {n \choose k}{k \choose m} (pp_jx)^m (p(1-p_j))^{k-m} (1-p)^{n-k}$$

i.e.

$$\displaystyle (pp_jx + 1 - pp_j)^n = \sum_{m=0}^{n} \sum_{k=m}^{n} {n \choose k}{k \choose m} p_j^m(1-p_j)^{k-m} p^{k}(1-p)^{n-k} x^m$$

Expanding the left hand side using binomial theorem and comparing the coefficients of $\displaystyle x^m$ gives the result.

-

Consider the following two-step process: Start with $n$ elements. Pick each one with probability $p$. Among the $k$ elements chosen in the first phase, pick each one with probability $p_j$. The left-hand side describes the probability that the final set is of size $m$.

We can also calculate this probability directly: every element is chosen to the final set with probability $pp_j$, whence the right-hand side.

-
Your answer is certainly correct. Indeed, it is a brief formulation of the answers given by me and Ralth. However, I consider this an indirect proof; I'm going to edit my question accordingly. –  Shai Covo Nov 15 '10 at 3:39
To be more specific, imagine this is a problem for a first year calculus course. –  Shai Covo Nov 15 '10 at 3:55

Writing the left-hand side as $$\sum\limits_{k = 0}^{n - m} {{n \choose k + m} p^{k + m} (1 - p)^{n - (k + m)} {k + m \choose m} p_j^m (1 - p_j )^{k + m - m} }$$ we find, after some algebra, that the original equation is equivalent to $$\sum\limits_{k = 0}^l {{l \choose k}p^k (1 - p)^{l - k} (1 - p_j )^k } = (1 - pp_j )^l ,$$ where $l (=n-m) \geq 0$. Since the case $p=0$ is satisfied ($0^0=1$), we assume that $p = x/y$, with $0 < x \leq y$. Substituting this leads straightforwardly to the equivalent equation $$\sum\limits_{k = 0}^l {{l \choose k}(x - x p_j)^k (y-x)^{l-k} = (y - xp_j)^l}.$$ By the binomial theorem, the left-hand side is equal to $[(x - xp_j ) + (y - x)]^l$, completing the proof.

-