Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 7 down vote accepted

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}$$


$$\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.

share|cite|improve this answer

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.