# Identity regarding the sum of products of binomial coefficients.

Consider the following toy problem

Person A and Person B have $$n$$ and $$n+1$$ fair coins respectively. If they both flip all their coins at the same time, what is the probability person B has more heads than person A?

The answer, regardless of $$n$$, is 50% -- which is pretty surprising. To convince myself, I derived the distribution for the difference in heads between B and A. Let $$D=B-A$$ and so $$\Pr(D=k)$$ is

$$\Pr(D=k \mid k>0) = \sum_{i=1}^{n+1} {n+1 \choose i}{n \choose i-k}2^{-2n-1}$$ and

$$\Pr(D=k \mid k\leq0) = \sum_{i=0}^{n} {n \choose i}{n+1 \choose i-k}2^{-2n-1}$$

If the answer to the question is 50%, this might mean that the distribution is symmetric about $$k=0$$. Naturally, I assumed that $$\Pr(k=1) = \Pr(k=0)$$ and tried to prove myself wrong or right.

Using Maple (computer algebra) I tried to evaluate the sums for each, and in each case I am told that the sums (excluding the factor of $$2^{-2n-1}$$) are equal and equivalent to

$${2n+1 \choose n}$$

See below

## Question

Are the sums which involve the product of binomial coefficients some sort of identity? If so, what is the name of said identity and how are the two equivalent (I presume the answer lies in some index manipulation).

• This $\frac12$ does not indicate symmetry about $0$. Even though $\Pr[A<B] = \frac12$, it is not true that $\Pr[A>B] = \frac12$, because there is also a chance that $A=B$. Commented May 29 at 0:34
• Right, I should have been more precise and said $\Pr(B>A) = \Pr(A \geq B)$ Commented May 29 at 0:39

Instead of $$D = B-A$$, consider $$D+n = B + (n-A)$$. This is the number of heads that B gets, plus the number of tails that A gets, so $$D+n$$ is a binomial with $$2n+1$$ trials and probability $$\frac12$$.
This immediately tells us that $$D+n$$ is symmetric about $$n+\frac12$$, and therefore $$D$$ is symmetric about $$\frac12$$. In particular, $$\Pr[D>0] = \Pr[D \le 0]$$.
Furthermore, $$\Pr[D=k] = \Pr[D+n = n+k] = \binom{2n+1}{n+k} 2^{-2n-1}$$ for $$k \in \{-n,\dots, n+1\}$$.
All this does not precisely answer the question, so let me just add that writing $$\Pr[D=k]$$ as $$\sum_i \Pr[B=i] \cdot \Pr[A=i-k]$$ and multiplying by $$2^{2n+1}$$ to get $$\binom{2n+1}{n+k} = \sum_i \binom {n+1}i \binom{n}{i-k} = \sum_i \binom {n+1}i \binom {n}{n+k-i}$$ is a special case of Vandermonde's identity: $$\sum_i \binom{a}{i} \binom{b}{c-i} = \binom{a+b}{c}.$$ Here, I omit the lower and upper bounds on the sum over $$i$$, because really they are taken over all $$i$$ where the summand is nonzero.
• Another way to see the symmetry: imagine that A and B each have $n$ "normal" coins, and B has an extra "tiebreaker" coin. The difference between the numbers of heads from just normal coins is symmetric about 0. Adding in the tiebreaker coin makes the difference symmetric about 1/2.