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?


1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .