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

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.$$

$$\sum_{p=0}^{n-1} \sum_{q=p+1}^{n+1} {n+1\choose q} {n\choose p}.$$
$$\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}.$$