evaluate $\sum_{i=0}^{n-1}\sum_{j=i+1}^{n+1} {n+1\choose j}{n\choose i}$

Question

Evaluate $\sum_{i=0}^{n-1}\sum_{j=i+1}^{n+1} {n+1\choose j}{n\choose i}$.

Below is a summary of a solution based off of a problem in the summation chapter of the book Problem Solving Through Problems by Loren Larson.

Multiply both sides of the sum by $\dfrac{1}{2^{2n+1}}.$

Consider a matching game played with two players A and B and $2n+1$ coins. Player $A$ flips $n+1$ coins and picks $n$ of them so that the number of heads flipped is maximal. Player $B$ flips $n$ coins. The player with the most heads flips wins, with ties going to B.

Then the probability $A$ wins is $\sum_{i=0}^{n-1} P(\text{ B flips i heads }) \sum_{j=i+1}^n P(\text{ A flips j heads } | \text{ B flips i heads }) = \sum_{i=0}^{n-1} P(\text{ B flips i heads }) \sum_{j=i+1}^n P(\text{ A flips j heads }) = \sum_{i=0}^{n-1} {n\choose i}\dfrac{1}{2^n}\sum_{j=i+1}^n {n+1\choose j}(\dfrac{1}2)^{n+1}$

Note that the game can be reformulated as follows: players A and B both flip $n$ coins and the one with the most heads flipped wins if there's no tie. If they both flip $n$ heads, then player B wins. If they flip less than n heads and there's a tie, then player A flips the $(n+1)$st coin and wins if it's heads and loses otherwise.

In this case, player B wins exactly two more times than player A (when both players flip n heads). So the probability player A wins is $1-P(\text{B wins}) = 1 - \dfrac{\dfrac{1}2 (2^{2n+1}+2)}{2^{2n+1}} = \dfrac{2^{2n}-1}{2^{2n+1}}.$

Hence the desired answer is $2^{2n}-1.$

I was wondering if there was a more elementary approach using basic combinatorial identities such as the hockey-stick identity, the Binomial theorem, the identity ${n\choose i} = \dfrac{n}i {n-1\choose i-1},$ etc? Basic rearranging gives that the sum in question equals $\sum_{j=1}^{n+1} {n+1\choose j} \sum_{i=0}^{j-1} {n\choose i}-1.$

Answer 1

We seek to evaluate

$$\sum_{p=0}^{n-1} \sum_{q=p+1}^{n+1} {n+1\choose q} {n\choose p}.$$

This is

$$\sum_{p=0}^{n-1} {n\choose p} \sum_{q=0}^{n-p} {n+1\choose q} \\ = \sum_{p=0}^{n-1} {n\choose p} [v^{n-p}] \frac{1}{1-v} \sum_{q\ge 0} {n+1\choose q} v^q \\ = [v^n] \frac{1}{1-v} \sum_{p=0}^{n-1} {n\choose p} v^p (1+v)^{n+1} \\ = -1 + [v^n] \frac{1}{1-v} (1+v)^{n+1} \sum_{p=0}^{n} {n\choose p} v^p \\ = -1 + [v^n] \frac{1}{1-v} (1+v)^{2n+1} \\ = -1 + \sum_{q=0}^n {2n+1\choose q} \\ = -1 + \frac{1}{2} 2^{2n+1} = -1 + 2^{2n}.$$