Finite Double Sum $\sum_{j=0}^n\sum_{i=0}^j \binom {n+1}{j+1}\binom ni =2^{2n}$ The problem is given in a combinatorics class study sheet. I cannot prove, and actually I am not sure if there was a mistake in the question or not. I tried for a few small n's e.g. 1, 2 and it holds. $\\$
I need to show that $\\$ $\mathop{\sum_{j=0}^{n}\sum_{i=0}^{j}}$ $n+1 \choose j+1$ $n \choose i $ = $2^{2n}$  $\forall n$ $\in$ $\mathbb{Z}^{+}$ 
 A: We give a probabilistic interpretation. By changing from probabilities to counts, we get a combinatorial interpretation.
Alicia tosses a fair coin $n+1$ times, and Beti tosses a fair coin $n$ times. Alicia wins if she has more heads than Beti. 
Our double sum, divided by $2^{2n+1}$, gives the probability that Alicia wins. We will show that this probability is $\frac{1}{2}$.  Then multiplying by $2^{2n+1}$ yields our desired result. 
Imagine that the two players each toss their coins simultaneously $n$ times. If Alicia is leading after $n$ tosses, she will win. If Beti is leading after $n$ tosses, then Beti will win. By symmetry these two events are equally likely.
And if they are tied after $n$ tosses, then with probability $\frac{1}{2}$, Alicia will get a head on the $(n+1)$-th toss, and win. And with probability $\frac{1}{2}$ she will get a tail and lose. 
A: The identity as shown in the question is correct.
$$\begin{align}
\sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom ni
&=\sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom n{n-i}\\
&=\sum_{j=0}^n\sum_{r=0}^j\binom {n+1}{j+1}\binom n{n+r-j}
&&\text{(putting }r=j-i)\\
&=\sum_{r=0}^n\sum_{j=r}^n\binom {n+1}{j+1}\binom n{n+r-j}
&&\text{(swapping order of indices)(}0\le r\le j\le n )\\
&=\sum_{r=0}^n\binom {2n+1}{n+1+r}
&&\text{(Vandermonde)}\\
&\color{lightgrey}{=\frac 12 \sum_{r=0}^n\binom {2n+1}{n-r}+\binom {2n+1}{n+1+r}}\\
&\color{lightgrey}{=\frac 12 \sum_{r=0}^{2n+1} \binom {2n+1}r}\\
&=\frac 12 \cdot 2^{2n+1}\\
&=2^{2n}\qquad\blacksquare\end{align}$$

Another approach:
$$\begin{align}
\sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom ni
&=\sum_{j=0}^n\sum_{i=0}^j \left[\binom nj+\binom n{j+1}\right]\binom ni\\
&=\underbrace{\sum_{\large 0\le i\color{red}\le j\le n}\binom nj\binom ni}_*+\binom n{j+1}\binom ni\\
&=\overbrace{\sum_{\large 0\le i\color{red}= j\le n}\binom nj\binom ni+\sum_{\large 0\le i\color{red}<j\le n}\binom nj\binom ni}^*+\sum_{\large 0\le i\color{red}< j\le n}\binom nj\binom ni\\
&=\sum_{\large 0\le i\color{red}=j\le n}\binom nj\binom ni+2\sum_{\large 0\le i\color{red}< j\le n}\binom nj\binom ni\\
&=\sum_{\large 0\le i\color{red}=j\le n}\binom nj\binom ni+\sum_{\large 0\le i\color{red}\neq j\le n}\binom nj\binom ni&&\text{(by symmetry)}\\
&=\sum_{j=0}^n\sum_{i=0}^n\binom nj\binom ni&&\text{(**)}\\
&=\sum_{j=0}^n\binom nj\sum_{i=0}^n\binom ni\\\\
&=2^n\cdot 2^n\\\\
&=2^{2n}\qquad\blacksquare
\end{align}$$
** as pointed out by Alex in a comment on the original question!
A: Here is another variation of the theme based upon two observations.

The first observation is the calculation of the double sum of the complete region $$0\leq i,j\leq n$$ is simple.
\begin{align*}
\sum_{j=0}^n\sum_{i=0}^{n}&\binom{n+1}{j+1}\binom{n}{i}\\
&=\sum_{j=1}^{n+1}\binom{n+1}{j}\sum_{i=0}^{n}\binom{n}{i}\tag{1}\\
&=\left(2^{n+1}-1\right)2^n\\
&=2\cdot4^n-2^n
\end{align*}

Comment:


*

*In (1) we rearrange the double sum and shift the index $j$ by one.



The second observation is based upon symmetry. We could expect the expression of the double sum with the upper triangle $$0\leq j < i\leq n$$ as index range is very similar to the expression with the lower triangle $$0\leq i\leq j \leq n$$ as index range. Indeed, we obtain
  \begin{align*}
\sum_{j=0}^{n}&\sum_{i=j+1}^n\binom{n+1}{j+1}\binom{n}{i}\\
&=\sum_{j=0}^{n}\sum_{i=n-j+1}^n\binom{n+1}{n-j+1}\binom{n}{i}\tag{2}\\
&=\sum_{j=0}^{n}\sum_{i=0}^{j-1}\binom{n+1}{n-j+1}\binom{n}{i+n-j+1}\tag{3}\\
&=\sum_{j=1}^{n}\sum_{i=0}^{j-1}\binom{n+1}{j}\binom{n}{i}\tag{4}\\
&=\sum_{j=0}^{n-1}\sum_{i=0}^{j}\binom{n+1}{j+1}\binom{n}{i}\tag{5}\\
&=\sum_{j=0}^{n}\sum_{i=0}^{j}\binom{n+1}{j+1}\binom{n}{i}-2^n\tag{6}\\
\end{align*}

Comment:


*

*In (2) we replace $j\rightarrow n-j$

*In (3) we shift the index $i$ to start from $0$

*In (4) we use $\binom{n}{k}=\binom{n}{n-k}$ and we replace $i\rightarrow j-1-i$. We also note that $j$ starts with $j=1$ due to the upper index of $i$ equal to $j-1$.

*In (5) we shift the index $j$ by one.

*In (6) we add $j=n$ to the double sum and subtract $2^n$ accordingly.

We see, the double sum with the upper triangle as index range can be transformed to the double sum with the lower triangle as index range. Putting all together we obtain
\begin{align*}
  \sum_{j=0}^n&\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}+
  \sum_{j=0}^n\sum_{i=j+1}^n\binom{n+1}{j+1}\binom{n}{i}\\
  &=2\sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}-2^n
  \end{align*}
We obtain with (1)
\begin{align*}
  2\sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}-2^n&=2\cdot 4^n-2^n\\
  \end{align*}
resp.
\begin{align*}
  \sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}&=4^n\\
  \end{align*}
and the claim follows.

A: Define $$F_n:=\sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom ni$$where $n\ge0.$ Then keeping in mind the symmetry of binomial coefficients,\begin{align}F_n
&=\sum_{j=0}^n\sum_{i=0}^j \left[\binom nj+\binom n{j+1}\right]\binom ni\\
&=\sum_{j=0}^n\sum_{i=0}^j \binom n{j}\binom ni + \sum_{j=0}^n\sum_{i=0}^{j+1} \binom n{j+1}\binom ni-\sum_{j=0}^n\binom n{j+1}^2\\
&=\sum_{j=0}^n\sum_{i=0}^j \binom n{j}\binom ni + \sum_{j=1}^n\sum_{i=0}^{j} \binom n{j}\binom ni-\sum_{j=1}^n\binom n{j}^2\\
&=2\sum_{j=0}^n\sum_{i=0}^j \binom n{j}\binom ni -\sum_{j=0}^n\binom n{j}^2\\
&=\left(\sum_{i=0}^n \binom ni\right)^2\\\\
&=2^{2n}
\end{align}
Q.E.D.
