# How to prove $\sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{i+j\choose n}=2^n{2n\choose n}$?

Numerical calculation suggests the following two combinatorial identities: $$\sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{i+j\choose n}=2^n{2n\choose n},\\ \sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{n\choose i+j}={3n\choose n}.$$ Proofs or references are all welcome.

For the first one: pick $i$ numbers from 1 to $n$, then $j$ numbers from $n+1$ to $2n$, then select $n$ of the $i+j$ picked numbers. One ends with an $n$-element subset of $1, \ldots, 2n$. Each such resulting subset can be generated in $2^n$ ways, once for each subset of $[1, \ldots, 2n] \setminus X$. (If $X$ is the resulting set, let $A = X\cap[1,\ldots, n]$ and $B = X \cap[n+1, \ldots, 2n]$; denote $a=|A|$ and $b=|B|$. Then $X$ can be obtained by selecting $A\cup Y$ and $B\cup Z$. There are $2^{n-a}$ ways for $Y$ and $2^{n-b}$ ways for $Z$, hence $2^{n-a}2^{n-b} = 2^n$ ways for $X$.)
For the second one: $\binom{3n}{n}$ is the number of ways to pick $n$ numbers from $1, 2, \ldots, 3n$. You can pick $i$ from the first $n$, $j$ from the next $n$, and are left to pick $n-(i+j)$ from the last $n$ (or to ignore $i+j$ from the last $n$). The last factor is 0 if you have already picked more than $n$ from the first two buckets.
I do not have the complete proof but still here is something interesting for the first identity $\sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{i+j\choose n} = \sum_{s=0}^{2n}\sum\limits_{i+j=s}{n\choose i}{n\choose j}{i+j\choose n}=\sum_{s=0}^{2n}{s\choose n}\sum\limits_{i+j=s}{n\choose i}{n\choose j}$ and the internal sum can be written $\sum\limits_{i+j=s}{n\choose i}{n\choose j}=\sum_{k=0}^s{n \choose k}{n \choose s-k} \stackrel{Vandermonde \ identity}{=} {2n \choose s}$ therefore $\sum_{i=0}^n\sum_{j=0}^n{n\choose i}{n\choose j}{i+j\choose n} = \sum_{s=0}^{2n}{s \choose n}{2n \choose s}$
• I follows you results. $\sum_{s=0}^{2n}{s\choose n}{2s\choose n}={2n\choose n}\sum_{s=0}^{2n}{n\choose 2n-s}={2n\choose n}2^n$. This completes the proof of the first identity. – Ji-Cai Liu May 17 '17 at 14:51