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.

Solutions Collecting From Web of "Non-probabilistic proofs of a binomial coefficient identity from a probability question"

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.

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.