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.

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.
