Sum it all

Suppose that $A$ tosses $n$ fair coins, and that $B$ tosses $n+1$ . Then the probability that $A$ tosses $k$ Heads is $2^{-n}{n \choose k} \hspace{2cm} 0 \le k \le n$ while the probability that $B$ tosses $r$ Heads is $2^{-n-1}{n+1 \choose r} \hspace{2cm} 0 \le r \le n+1$ Thus, if $p$ is the probability that $B$ tosses more Heads than does $A$ , then $p \; = \; \sum_{k < r} 2^{-n} {n \choose k} \times 2^{-n-1}{n+1 \choose r}$ and so the sum we are interested in is $2^{2n+1}p$ .

The fact that $p=\tfrac12$ is a classic problem. Here is a proof.

Let $a$ be the number of Heads that $A$ tosses, and let $b$ be the number of Heads that $B$ tosses. Then $a < b \; \Leftrightarrow\; a+1 \le b \; \Leftrightarrow \; n-a \ge n+1-b$ (since $a,b$ are integers) and so $\mathbb{P}[a < b] \; = \; \mathbb{P}[n-a \ge n+1-b] \; = \; 1 - \mathbb{P}[n-a < n+1-b]$ But $n-a$ is the number of Tails that $A$ tosses, while $n+1-b$ is the number of Tails that $B$ tosses. In other words, the probability that $B$ tosses more Heads than $A$ is $1$ minus the probability that $B$ tosses more Tails than $A$ . By symmetry, the probabilities that $B$ tosses more Heads than $A$ , and that $B$ tosses more Tails than $A$ , must be the same. Hence they are both equal to $\tfrac12$ . Thus $p=\tfrac12$ , and so the desired sum is $2^{2n} = \boxed{4^n}$ .

$S=\sum_{0\leq k<r\leq n+1}\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}n+1\\ r\end{array}\right)= \sum_{k=0}^{n}\sum_{r=k+1}^{n+1}\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}n+1\\ r\end{array}\right)= \sum_{k=0}^{n}\left(\begin{array}{c}n\\ k\end{array}\right) \left(2^{n+1} - \sum_{r=0}^k \left(\begin{array}{c}{n+1}\\ r\end{array}\right) \right )= 2^{2n+1} - S\Rightarrow 2S= 2^{2n+1} or S=2^{2n}$

The given sum is $\sum_{0 \leq k< r \leq n+1} \dbinom {n}{k} \dbinom {n+1}{r}$

This can be grouped as

$(\dbinom {n}{0}\dbinom {n+1}{1}+\dbinom {n}{1}\dbinom {n+1}{2}+......+\dbinom {n}{n}\dbinom {n+1}{n+1})$ +

$(\dbinom {n}{0}\dbinom {n+1}{2}+\dbinom {n}{1}\dbinom {n+1}{3}+......+\dbinom {n}{n-1}\dbinom {n+1}{n+1})$ +............

$(\dbinom {n}{0}\dbinom {n+1}{n+1})$

now each of the brackets represent the coefficients of positive powers of $x$ in the expansion of

$(1+\dfrac{1}{x})^{n}\times (1+x)^{n+1}$

now this expression can be simplified as

$(1+\dfrac{1}{x})^{n}\times (1+x)^{n+1}=((1+\dfrac{1}{x})\times (1+x))^{n}(1+x)=(2+x+\dfrac{1}{x})^n(1+x)=(\dfrac{x^2+2x+1}{x})^n(1+x)=\dfrac{(1+x)^{2n+1}}{x^n}$

we need to find the sum of coefficients of positive powers of $x$ , there are $2n+2$ terms in the expansion and we need to find the sum of coefficients of the last $n+1$ terms

we know $\dbinom {n}{r}=\dbinom {n}{n-r}$

Thus the sum of coefficients of first $n+1$ terms will be same as sum of coefficients of final $n+1$ terms

Total sum of coefficients= $2^{2n+1}$

thus sum of coefficients of final n+1 terms is $\dfrac{2^{2n+1}}{2}=2^{2n}=\boxed{4^n}$

Here is a solution that is similar to Mark's, but more directly presented.

The expression is equivalent to the number of ways that $A$ can toss $n$ coins and $B$ can toss $n+1$ coins, where the number of heads that A gets is strictly fewer than the number of heads that B gets.

We will create a double-counting bijection in the following way:
Let $A$ toss $n$ coins and $B$ toss $n+1$ coins. There are $2 ^ n \times 2 ^ {n+1}$ ways to do so.

If A has strictly fewer heads than B, that is the case that we want to count.
If A has at least as many heads as B. Say $A$ flipped $a$ heads and $B$ flipped $b$ heads with $a \geq b$ . If we filp all of the coins, then $A$ has $n-a$ heads and $B$ has $n+1 - b$ heads. Since $n - a \leq n - b < n + 1 - b$ , hence we are also back in the case that we want to count.

Conversely, given any "A gets strictly fewer heads than B", we can map it to these 2 cases, by flipping no coins and flipping all the coins.

Hence, the number of ways is $\frac{1}{2} \times 2^{2n+1} = 2^{2n} = 4^n$ .

$S= \displaystyle \sum_{0 \leq k < r \leq n+1} \dbinom {n}{k} \dbinom {n+1}{r}$

$S= \displaystyle \sum_{0 \leq k < r \leq n+1} \dbinom {n}{n-k} \dbinom {n+1}{(n+1)-r}$

Adding the two equations, we have

$\begin{aligned} 2S&= \displaystyle \sum_{0 \leq k \leq n, 0 \leq r \leq n+1} \dbinom {n}{k} \dbinom {n+1}{r} \\ 2S&=( \displaystyle \sum_{0 \leq k \leq n} \dbinom {n}{k})( \displaystyle \sum_{0 \leq r \leq n+1} \dbinom {n+1}{r}) \\ 2S&=(2^{n})(2^{n+1}) \\ 2S&=2^{2n+1} \\ S&=2^{2n}=\boxed{4^{n}} \end{aligned}$

Let $f(a, b) = \binom{n}{a} \binom{n}{b}$ . Note that $f(n+1, b) = 0$ because $\binom{n}{n+1} = 0$ .

Observe that $\binom{n}{k} \binom{n+1}{r} = \binom{n}{k} \binom{n}{r-1} + \binom{n}{k} \binom{n}{r} = f(k, r-1) + f(r, k)$ . Given any $a, b$ satisfying $0 \le a \le n-1, 0 \le b \le n$ , we can find exactly one $k, r$ where $k < r$ such that $\binom{n}{k} \binom{n+1}{r}$ involves summing $f(a, b)$ : indeed, if $a \le b$ , then we pick $k = a, r = b+1$ , and if $a > b$ , then we pick $r = a, k = b$ .

In other words, we can represent the sum as $\sum_{a=0}^{n+1} \sum_{b=0}^n f(a, b)$ , since we showed each $f(a, b)$ appears exactly once somewhere in $\binom{n}{k} \binom{n+1}{r}$ .

Since $f(n+1, b) = 0$ , we can restrict the sum to $\sum_{a=0}^n \sum_{b=0}^n f(a, b)$ . Now we expand $f(a, b)$ and notice that we can factor out $\binom{n}{a}$ , getting $\sum_{a=0}^n \left( \binom{n}{a} \cdot \sum_{b=0}^n \binom{n}{b} \right)$ . But $\sum_{b=0}^n \binom{n}{b} = 2^n$ , and we can factor this out of the summation, to get $2^n \cdot \sum_{a=0}^n \binom{n}{a} = 2^n \cdot 2^n = \boxed{4^n}$ .