# Evaluating a binomial sum with a probabilistic interpretation

Evaluate the following double summation over all acceptable values of $$m$$ and $$k$$:

$$S=\sum_{0 \leq k < m \leq n+1} \binom {n+1}{m}\binom {n}{k}$$

This sum arose in a probability question a friend of mine came across in her homework, in which two people A and B were tossing $$(n+1)$$ and $$n$$ coins respectively and $$P(m,k)$$ was the probability that A throws $$m$$ heads and B throws $$k$$ heads. Evidently, since both events are independent, $$P(m,k)=\binom{n+1}{m} \binom{n}{k} \dfrac{1}{2^{2n+1}}$$

If we wish to sum the values of $$P(m,k)$$ over the conditions $$0 \leq k < m \leq n+1$$, that can be interpreted as the sum of probabilities of all the scenarios in which A gets more heads than B.

To calculate this probability, suppose that $$P$$ is the probability that A throwing more heads than B when both parties have thrown $$n$$ coins each. By symmetry, the probability of $$B$$ throwing more heads than $$A$$ is also $$P$$. Hence, the probability of A and B having thrown the same number of heads in tossing $$n$$ coins is $$(1-2P)$$. Now, A can throw more heads than B in two ways;

(i) $$A$$ has thrown more heads than B in $$n$$ tosses. This event has probability $$P$$ as defined before.

(ii) $$A$$ and $$B$$ are tied till the $$n$$th toss and on the $$(n+1)$$th coin toss, $$A$$ gets a head. The probability of this scenario is $$(1-2P) . 1/2$$

Hence, this sum would be equal to the sum of the probabilities of the above two scenarios i.e. equal to $$1/2$$.

Hence, $$S=2^{2n}$$. I'm looking for a solution to this problem using the properties of binomial coefficients to evaluate this sum now. I've seen a similar problem evaluating $$\binom {n}{k} \binom {n}{m}$$ (say $$S'$$) under the same conditions by expressing the square of the sum of all binomial coefficients and using symmetry to observe that $$2^{2n}=\binom{2n}{n} + 2S'$$ but that reasoning does not apply here since there is no symmetry in the products. How do I solve this problem using the properties of binomial coefficients and sums only?

Obviously: $$S(0)=\sum_{0 \le k < m \le 1} \binom {1}{m}\binom {0}{k}=1=4^0.$$
Assume $$S(n)=4^n$$. Then \begin{align} S(n+1)&=\sum_{0 \le k < m \le n+2} \binom {n+2}{m}\binom {n+1}{k}\\ &=\sum_{0 \le k < m \leq n+2}\left[\binom {n+1}{m}+\binom {n+1}{m-1}\right]\cdot\left[\binom {n}{k}+\binom {n}{k-1}\right]\\ &=\sum_{0 \le k < m \leq n+2}\left[\binom {n+1}{m}\binom {n}{k}+\binom {n+1}{m-1}\binom {n}{k}+\binom {n+1}{m}\binom {n}{k-1}+\binom {n+1}{m-1}\binom {n}{k-1}\right]\\ &=4^{n}+[4^{n}+X(n)]+[4^n-X(n)]+4^{n}=4^{n+1}, \end{align} where $$X(n)=\sum_{0 \le k \le n}\binom {n+1}{k}\binom {n}{k}$$. By induction the formula $$S(n)=4^n$$ is proved.
In the last line we took into account that $$\binom nm=0$$ for $$m<0$$ and $$m>n$$ as well as \begin{align} \sum_{0 \leq k < m \leq n+2}\binom {n+1}{m-1}\binom {n}{k}&= \sum_{0 \leq k < m+1 \le n+2}\binom {n+1}{m}\binom {n}{k}\\ &=\sum_{0 \leq k < m \leq n+1}\binom {n+1}{m}\binom {n}{k}+ \sum_{0 \leq k \leq n}\binom {n+1}{k}\binom {n}{k} \end{align} and \begin{align} \sum_{0 \leq k < m \leq n+2}\binom {n+1}{m}\binom {n}{k-1}&= \sum_{0 \leq k < m-1 \leq n}\binom {n+1}{m}\binom {n}{k}\\ &=\sum_{0 \leq k < m \leq n+1}\binom {n+1}{m}\binom {n}{k}- \sum_{0 \leq k \leq n}\binom {n+1}{k+1}\binom {n}{k}. \end{align} The equality: $$\sum_{0 \leq k \leq n}\binom {n+1}{k+1}\binom {n}{k}=\sum_{0 \leq k \leq n}\binom {n+1}{k}\binom {n}{k}:=X(n)$$ follows from the antisymmetry property $$F(n,k)=-F(n,n-k)$$ valid for the function: $$F(n,k)=\left[\binom{n+1}{k+1}-\binom{n+1}k\right]\binom nk$$ which can be easily verified by direct substitution.