combinatorial argument that $ [\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}]^{2} = \sum_{k=0}^{2n}\binom{2n}{k}$

Question

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 ?

Answer 1

Let's say we have $n$ pizzas and they either have cheese or don't have cheese. Each pizza can have cheese or no cheese, $2$ choices for $n$ pizzas, so $2^n$ ways. However, you can also calculate it this way. First, find the number of ways to have $0$ no cheese and $n$ cheese. We can choose $0$ pizza to be no cheese, so $n \choose 0$. Also, we can have $1$ no cheese and $n-1$ cheese, so choose $1$ pizza to have $1$ no cheese out of $n$ pizzas, thus we get $n \choose 1$. See where we are going? We keep on calculating through and eventually get the sum ${n \choose 0} + {n \choose 1} + \dots + {n \choose {n-1}} +{n \choose n}$, and we know this is equal to $2^n$, so this sum squared should be $2^{2n}$

Now look at the right side. Each pizza can have cheese or no cheese, $2$ choices for $2n$ pizzas, so $2^{2n}$ ways. However, you can also calculate it this way. First, find the number of ways to have $0$ no cheese and $2n$ cheese. We can choose $0$ pizza to be no cheese, so $2n \choose 0$. Also, we can have $1$ no cheese and $2n-1$ cheese, so choose $1$ pizza to have $1$ no cheese out of $2n$ pizzas, thus we get $2n \choose 1$. See where we are going? We keep on calculating through and eventually get the sum ${2n \choose 0} + {2n \choose 1} + \dots + {2n \choose {n-1}} +{2n \choose n}$, and we know this is equal to $2^{2n}$.

So, we have shown both sides equal to $2^{2n}$, thus we are done.

Answer 2

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$$

Answer 3

Both sides count the number of subsets chosen from among $n$ men and $n$ women. The LHS does so by counting the number of men and women independently, conditioning on the number $k$ of each. The RHS does the count by conditioning on the number $k$ of people out of $2n$.

Answer 4

You can combine both combinatorial and analytical reasoning as follows. Given a set $\,A = \{a_1,a_2,\dots,a_n\}\,$ with $\,n\,$ elements, and a subset $\,S\subseteq A,\,$ for each $\,i\in\{1,2,\dots,n\}\,$ the binomial $\,x_i+y_i\,$ represents the condition that $\,a_i\in S.\,$ That is, the choice $\,x_i\,$ indicates that $\,a_i\in S\,$ and $\,y_i\,$ indicates that $\,a_i\notin S.\,$ Using the multiplicative principle of independent choices, the product $\,P_A:=(x_1+y_1)(x_2+y_2)\cdots(x_n+y_n)\,$ expands into a sum of monomials which represents all subsets of $\,A.\,$ If $\,B=\{b_1,b_2,\dots,b_m\}\,$ is another set disjoint from $\,A,\,$ and the disjoint union $\,C=A\cup B,\,$ then all the subsets of $\,C\,$ is represented by the product $\,P_C = P_AP_B\,$ where each subset $\,S\subseteq C\,$ is partitioned uniquely as $\,S=S_A\cup S_B.\,$ Here $\,x_{i+n}\,$ indicates that $\,b_i\in S_B\,$ and $\,y_{i+n}\,$ indicates that $\,b_i\notin S_B.\,$

Given this result, consider the special case where $\,x_i=x,\, y_i=y\,$ for all $\,i\,$. Then $$ P_A = (x+y)^n = \sum_{j=0}^n x^jy^{n-j}{n\choose j},$$ $$ P_B = (x+y)^m = \sum_{k=0}^m x^ky^{m-k}{m\choose k},$$ $$ P_C = (x+y)^{n+m} = \sum_{i=0}^{n+m} x^iy^{n+m-i}{n+m\choose i}. $$ When $\,n=m\,$ and $\,x=y=1\,$ your result follows.