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!
 A: 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.
A: Let us call the sum of the given series as $S$.
$$S = \sum_{k=0}^{n} \sum_{l=0}^{n} \binom{n}{k} \binom{n}{l} \binom{n}{k+l}$$
For the inner summation,$\binom{n}{k}$ is a constant and can be moved outside. We are left with:
$$S = \sum_{k=0}^{n} \binom{n}{k} \sum_{l=0}^{n}  \binom{n}{l} \binom{n}{k+l}$$
We first need to focus on how to find the value of the sum $\sum_{l=0}^{n}  \binom{n}{l} \binom{n}{k+l}$. Call it $S_1$ for now.
To do so, we can apply a bit of Binomial Theorem.
We know that:
$$(1+x)^n = 1 + \binom{n}{1}x + ... + \binom{n}{k}x^k + \binom{n}{k+1}x^{k+1} + ... + \binom{n}{n}x^n$$
We can also once again write the series in reverse:
$$(x+1)^n = x^n + \binom{n}{1}x^{n-1} + ... + \binom{n}{n-1}x + \binom{n}{n}$$
If you notice carefully, when we multiply out the above two Binomial sequences, all of the terms of the sequence $S_1$ appear as coefficients of $x^{n+k}$, i.e. the sequence
$$S_1 = \sum_{l=0}^{n}  \binom{n}{n-l} \binom{n}{k+l} = \binom{n}{k}\binom{n}{0} + \binom{n}{k+1}\binom{n}{1} + ... + \binom{n}{k+n}\binom{n}{n} $$
is nothing but the coefficient of $x^{n+k}$ in $(1+x)^{2n}$ = $\binom{2n}{n+k}$
In fact, we have discovered a useful result known as the Vandermonde Identity which states that in general:
$$\binom{m+n}{r}=\sum_{k=0}^r \binom{m}{k} \binom{n}{r-k}$$
Now that we have figured out $S_1$, $S$ reduces to:
$$S = \sum_{k=0}^{n} \binom{n}{k} \binom{2n}{n+k}$$
Rewriting $\binom{n}{k}$ as $\binom{n}{n-k}$ and applying Vandermonde again, we finally get:
$$S = \binom{3n}{2n} = \binom{3n}{n}$$
A: \begin{eqnarray*}
\sum_{k=0}^{n} \sum_{l=0}^{n} \binom{n}{k} \binom{n}{l} \binom{n}{k+l} &=& [x^0]: \sum_{k=0}^{n} \sum_{l=0}^{n} \binom{n}{k} \binom{n}{l} x^{-k-l} (1+x)^n \\
&=& [x^0]: \left(1+ \frac{1}{x} \right)^{2n} (1+x)^n \\
&=& [x^{2n}]:  (1+x)^{3n} = \binom{3n}{n}.\\
\end{eqnarray*}
