A combinatorial equality $\left(\sum_{k=0}^n\binom nk\right)^2=\sum_{k=0}^{2n}\binom {2n}{k}$?

Question

Prove or disprove that $$\left(\sum_{k=0}^n\binom nk\right)^2=\sum_{k=0}^{2n}\binom {2n}{k}$$ I cannot for the moment but it seems that it is true.

Answer 1

Hint:

Expand $\;(1+1)^n\;$ and $\;(1+1)^{2n}$.

Answer 2

By the binomial theorem: $$(\sum_{k-0}^n\binom{n}{k})^2=(\sum_{k=0}^n\binom{n}{k}1^{n-k}1^k)^2=((1+1)^n)^2=(1+1)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}1^{n-k}1^k$$

Answer 3

One way to look at it is the following: $ {2n\choose m} = \sum_{l=0}^m {n\choose l}{n\choose m-l}$

This is true because the LHS is the number of ways of choosing $m$ objects out of $2n$. THis is the same as choosing $l$ objects from the first $n$, and $m-l$ objects from the last $n$ objects, summed over all values of $l \in \{0,1,\ldots,m\}$.

Now, summing this over all values of $m \in \{0,1,\ldots,2n\}$ gives the result.

Answer 4

Probably not what you are after, but from a combinatorial point of view you even have: $$ \left( \begin{matrix} 2n \\ m \end{matrix} \right)= \sum_{k+l=m,\ \ 0\leq k,l\leq n} \left( \begin{matrix} n \\ k\end{matrix} \right) \left( \begin{matrix} n \\ l \end{matrix} \right) $$ Which states that picking $m$ balls from a collection of $n$ red balls and $n$ white balls may be done by picking $k$ red ones and $l$ white ones. Summing over all $m$ (whence over all possibly $k$ and $l$) gives the stated result.

Answer 5

It’s working much harder than necessary, but just for fun here’s a completely combinatorial proof that does not require evaluating either summation explicitly. Let $A$ and $B$ be two disjoint $n$-element sets. The lefthand side is

$$\left(\sum_{k=0}^n\binom{n}k\right)^2=\sum_{k=0}^n\sum_{\ell=0}^n\binom{n}k\binom{n}\ell=\sum_{0\le k,\ell\le n}\binom{n}k\binom{n}\ell\;.$$

For each pair $\langle k,\ell\rangle$ with $0\le k,\ell\le n$, $\binom{n}k$ can be interpreted as the number of $k$-element subsets of $A$, and $\binom{n}\ell$ as the number of $\ell$-element subsets of $B$. The term $\binom{n}k\binom{n}\ell$ therefore gives the number of ordered pairs $\langle X,Y\rangle$ such that $X$ is a $k$-element subset of $A$, and $Y$ is an $\ell$-element subset of $B$. When we sum these products over all pairs $\langle k,\ell\rangle$ with $0\le k,\ell\le n$, we must get the total number of ordered pairs $\langle X,Y\rangle$ such that $X\subseteq A$ and $Y\subseteq B$. In other words, we get $|\wp(A)\times\wp(B)|$.

Now look at the righthand side: $\binom{2n}k$ is the number of $k$-element subsets of the $2n$-element set $A\cup B$, and we’re summing over all of the possible values of $k$, so

$$\sum_{k=0}^{2n}\binom{2n}k$$

is just the number of subsets of $A\cup B$, i.e., $|\wp(A\cup B)|$. We’re done if we can find a bijection between $\wp(A)\times\wp(B)$ and $\wp(A\cup B)$, and it’s not hard to check that the map

$$h:\wp(A\cup B)\to\wp(A)\times\wp(B):X\mapsto\langle X\cap A,X\cap B\rangle$$

is indeed such a bijection, with inverse

$$h^{-1}:\wp(A)\times\wp(B)\to\wp(A\cup B):\langle X,Y\rangle\mapsto X\cup Y\;.$$

Of course if one knows that an $n$-element set has $2^n$ subsets, the original identity simply reduces to $\left(2^n\right)^2=2^{2n}$ without further ado.