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


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