Give a combinatorial argument with double counting showing that
$$ \Bigg[\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}\Bigg]^{2} = \sum_{k=0}^{2n}\binom{2n}{k}$$
I am unsure on how to approach this problem from a combinatorial argument perspective. I have found an analytical proof using the binomial theorem, but can't formulate an explanation in the former way.
From my understanding, $\displaystyle \sum_{k=0}^{n} {n \choose k}$ represents the number of ways we can chose a set of $k$ objects from a group of $n$ objects, for $k \le n$. So this quantity squared should be equivalent the number of ways to pick a set of $k$ objects from a group of $2n$ objects.
Could anyone provide me any hints on how to approach this problem combinatorically ?
Best Answer
Both sides describe the number of ways to select any number of elements from $2n$ elements (and are both equal to $2^{2n}$)
Let's write $A=\{1,\dots,n\}$ and $B=\{n+1,\dots,2n\}$.
Now the subsets of $A\cup B$ are in bijection to the pairs of a subset of $A$ and a subset of $B$.
$$\mathcal{P}(A\cup B) \to \mathcal{P}(A)\times \mathcal{P}(B)$$ $$S \mapsto (S\cap A, S \cap B)$$
Also $$|\mathcal{P}(A\cup B)| = \sum_{k=0}^{2n} |\{S\subseteq A\cup B \mid |S|=k\}| = \sum_{k=0}^{2n} \binom{2n}{k}$$ $$|\mathcal{P}(A)| = \sum_{k=0}^{n} |\{S\subseteq A \mid |S|=k\}| = \sum_{k=0}^{n} \binom{n}{k}$$ $$|\mathcal{P}(B)| = \sum_{k=0}^{n} |\{S\subseteq B \mid |S|=k\}| = \sum_{k=0}^{n} \binom{n}{k}$$
So $$RHS = |\mathcal{P}(A\cup B)| = |\mathcal{P}(A)||\mathcal{P}(B)| = LHS$$