proof of binomial identity involving double sum It's asked to simplify the sum
$$\displaystyle\sum_{0\le i <j\le n+1} \binom{n}{i} \times \binom{n+1}{j} $$
inspecting first values of $n$ shows the sum if apparently equal to $4^n$
I tried re-writing the sum as 
$$\displaystyle\sum_{j=1}^{n+1} \binom{n+1}{j} \displaystyle\sum_{i=0}^{j-1} \binom{n}{i}  $$ but that doesn't seem to lead us to the result.
Any suggestions are welcome.
Thanks.
 A: Starting from $$\sum_{0\le i <j\le n+1} \binom{n}{i} \binom{n+1}{j}$$
we split the second binomial to
$$\sum_{0\le i <j\le n+1} \binom{n}{i} \binom{n}{j} + \sum_{0\le i <j\le n+1} \binom{n}{i} \binom{n}{j-1}$$ and reindex to
$$\sum_{0\le i <j\le n} \binom{n}{i} \binom{n}{j} + \sum_{0\le i \le k \le n} \binom{n}{i} \binom{n}{k}$$
Now we can expand both of those terms by symmetry to
$$\frac{\left[\sum_{0\le i\le n} \binom{n}{i}\right]\left[\sum_{0\le j\le n} \binom{n}{j}\right] - \sum_{0\le \iota\le n} \binom{n}{\iota}^2}{2} + \frac{\left[\sum_{0\le i\le n} \binom{n}{i}\right]\left[\sum_{0\le k\le n} \binom{n}{k}\right] + \sum_{0\le \kappa\le n} \binom{n}{\kappa}^2}{2}
$$
and the rest is easy.

Or even more straightforwardly, rename variables in the second sum to get 
$$\sum_{0\le i <j\le n} \binom{n}{i} \binom{n}{j} + \sum_{0\le j \le i \le n} \binom{n}{j} \binom{n}{i} = \sum_{0\le i\le n \\ 0\le j\le n} \binom{n}{i} \binom{n}{j}$$
This points the way to a bijective proof: interpret the original sum as the number of ways of putting a red hat on $i$ out of $n$ people and a green hat on $j > i$ out of ($n$ people and one dressmaker's dummy). Then if there's a green hat on the dummy, take the green hat away from the dummy and each person who has one and give a green hat to each person who doesn't have one. There are at most $4^n$ resulting hat distributions (every person can have no hats, a red hat, a green hat, or both hats), every one is possible (if there are more green hats than red hats then we know that the dummy didn't receive a hat; otherwise we know that the dummy did receive a hat), and every one is obtained in precisely one way.
A: Hint: For every $(i,j)$ with $0\leq i\leq n$, $0\leq j\leq n+1$ we have either $i<j$ or $n-i<n+1-j$ but not both.  So
$$
\sum_{0\leq i<j\leq n+1}\binom{n}{i}\binom{n+1}{j}
=\sum_{i,j}\binom{n}{i}\binom{n+1}{j}-\sum_{\substack{n-i<n+1-j\\0\leq i\leq n\\0\leq j\leq n-1}}\binom{n}{i}\binom{n+1}{j}
$$
and now use $\binom{n}{i}=\binom{n}{n-i}$, $\binom{n+1}{j}=\binom{n+1}{n+1-j}$.
A: You can use the identity ${n+1\choose j}={n\choose j}+{n\choose j-1}$. 
$$\sum_{0\le i <j\le n+1} \binom{n}{i} \cdot \binom{n+1}{j}=\sum_{0\le i <j\le n+1} \binom{n}{i} \times\left( {n\choose j}+{n\choose j-1}\right)$$
$$\sum_{0\le i <j\le n+1} \binom{n}{i}  {n\choose j}+\sum_{0\le i <j\le n+1} \binom{n}{i} \times{n\choose j-1}$$
index shift for the second sum: $j-1\to j$ 
$$\sum_{0\le i <j\le n+1} \binom{n}{i}  {n\choose j}+\sum_{0\le i \leq j\le n+1} \binom{n}{i} \times{n\choose j}$$
Using the symmetry argument we have $\sum\limits_{0\le i \leq j\le n+1} \binom{n}{i} \times{n\choose j}=\sum\limits_{0\le j \leq i\le n+1} \binom{n}{i} \times{n\choose j}$ we get
$$\sum\limits_{i=0}^{n+1} \sum\limits_{j=0}^{n+1} {n \choose j}\cdot {n \choose i}=\sum\limits_{i=0}^{n+1}  {n \choose i} \cdot\sum\limits_{j=0}^{n+1} {n \choose j}=4^n$$
