0
$\begingroup$

This question already has an answer here:

I've stumbled upon this lemma a few times in my textbook: $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}^2=\begin{pmatrix}2n\\n\end{pmatrix}$$ I've been trying to prove it, but I simply can't seem to see a connection. I've been trying to use proof by induction, but I can't express the statement for $n+1$ via the statement for $n$.

How do I prove it?

$\endgroup$

marked as duplicate by user147263, Newb, Chris Janjigian, Thomas, Jonas Meyer Dec 27 '14 at 20:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

$$ {n \choose k} = {n \choose n-k} $$ Then we can divide $2n$ objects into two groups. Form one group we choose $k$ from the other $n-k$ and we assuming all possibilities for $k$. Hence we get: $$ {2n \choose n}=\sum_{k=0}^n{n \choose k} {n \choose n-k} = \sum_{k=0}^n{n \choose k}^2 $$

$\endgroup$
1
$\begingroup$

Since $\dbinom n k= \dbinom n {n-k}$, the identity $$ \sum_{k=0}^n \binom n k ^2 = \binom {2n} n $$ is the same as $$ \sum_{k=0}^n \binom n k \binom n {n-k} = \binom {2n} n. $$ So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $\dbinom n k \cdot \dbinom n {n-k}$ ways. The number of Democrats is in the set $\{0,1,2,\ldots,n\}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.

$\endgroup$
0
$\begingroup$

Consider the coefficient of $x^n$ in $(1+x)^{2n}$. We have $$ (1+x)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^k=(1+x)^n(1+x)^n= \Big(\sum_{k=0}^{n}\binom{n}{k}x^k\Big)\Big(\sum_{k=0}^{n}\binom{n}{k}x^{n-k}\Big). $$ The coefficient of $x^n$ is equal to $\binom{2n}{n}$ in the left hand side.

The coefficient of $x^n$ is equal to $\sum_{k=0}^n\binom{n}{k}^{\!2}$ in the right hand side.

$\endgroup$
0
$\begingroup$

It seems the following.

$$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}=(1+1)^n=2^n.$$ $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}^2=\begin{pmatrix}2n\\n\end{pmatrix}$$

To prove the last inequality it suffice to calcuate the coefficient by $x^n$ at both sides of the equality

$$(1+x)^n(1+x)^n=(1+x)^{2n}.$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.