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 of getting three zeros when sampling a set, 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.
 A: 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.
A: 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.
A: 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.
