how to evaluate this sum of binomial coefficients

Question

I am reading Jaynes' "probability theory: the logic of science".

He occasionally makes derivations from formula's with binomial coefficients that perplex me, but he seems to consider them trivial.

For example, he considers it "readily seen" that the following: $$\left( {\matrix{n \\r}}\right)\sum_{R=0}^N \left(\matrix {N-n \\R-r}\right)g^R(1-g)^{N-R}$$ is equal to $$\left( {\matrix{n \\r}}\right)g^r(1-g)^{n-r} $$

How are we supposed to derive this? (and similar equations with factorials/binomial coefficients?)

Answer 1

Try to make a binomial sum appear, and use the Binomial Theorem: $$\begin{align} \sum_{R=0}^N \binom{N-n}{R-r}g^R(1-g)^{N-R} &= g^r(1-g)^{n-r} \sum_{R=0}^N \binom{N-n}{R-r}g^{R-r}(1-g)^{N-n-(R-r)}\\ &= g^r(1-g)^{n-r} \sum_{k=-r}^{N-n} \binom{N-n}{k}g^{k}(1-g)^{(N-n)-k}\\ &= g^r(1-g)^{n-r} \sum_{k=0}^{N-n} \binom{N-n}{k}g^{k}(1-g)^{(N-n)-k}\\ &= g^r(1-g)^{n-r} (g+(1-g))^{N-n}\\ &= g^r(1-g)^{n-r} 1^{N-n} = g^r(1-g)^{n-r} \end{align}$$

Answer 2

When a binomial identity looks like a sum of probabilities it is convenient to consider a combinatorial interpretation.

Let $A$ and $B$ be disjoint sets of $n$ and $N-n$ elements respectively. Construct a subset $S$ of $A$ by deciding for each element in $A$ with probability g whether it belongs to $S$. Check that the probaility for this set to have $r$ elements is ${n\choose r}g^r(1-g)^{n-r}$.

This is also equal to the probability that a subset $T$ of $A\cup B$ (with similarly every element chosen with probability g) has $r$ elements in $A$. Now compute this last probability as a sum over $R$, the number of elements of $T$ that are in $B$ (I'll let that to you).