Combinatorial Proof for $\binom{3n}{n}$ I am trying to prove the following equality:
$\sum_{k=0}^{n} \sum_{l=0}^{n} \binom{n}{k} \binom{n}{l} \binom{n}{k+l} = \binom{3n}{n}$
This is what I have so far:
$\sum_{k=0}^{n} \sum_{l=0}^{n} \binom{n}{k} \binom{n}{l} \binom{n}{k+l} = \sum_{k=0}^{n}\binom{n}{k} \sum_{l=0}^{n}\binom{n}{l} \sum_{k=0}^{n} \sum_{l=0}^{n}\binom{n}{k+l}$
$\implies 2^{n} \cdot 2^{n} \sum_{k=0}^{n} \sum_{l=0}^{n}\binom{n}{k+l}$
$\implies 2^{2n} \cdot \sum_{k=0}^{n} \sum_{l=0}^{n}\binom{n}{k+l}$
I got stuck here, and I'm having trouble manipulating the second term. I would appreciate any help on this proof!

Here's a combinatorial proof:
Let $X$ be a set of $3n$ elements. Let's count the number of subsets of $X$ that have exactly $n$ elements. This is of course $\binom{3n}{n}$. However, here's another way to count them that yields your LHS:
Decompose $X$ into three disjoint subsets $X=X_1\cup X_2\cup X_3$ such that $|X_i|=n$ for $i=1,2,3$. A subset $U\subseteq X$ now corresponds to a triple of subsets $U_i\subseteq X_i$ for $i=1,2,3$. When $U$ has $n$ elements, we have $|U_3|=n-k-l$ for $k=|U_1|$ and $l=|U_2|$. Hence, counting all the triples $U_1,U_2,U_3$ that yield $n$ element subsets $U\subseteq X$ we get
$$
\sum_{k=0}^n \sum_{l=0}^n \binom{n}{k} \binom{n}{l} \binom{n}{n-k-l}.
$$
Since $\binom{n}{n-k-l}=\binom{n}{k+l}$ (by considering complements in $X_3$), this proves your identity.
