5
$\begingroup$

Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$

The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$.

Any help?

$\endgroup$
9
$\begingroup$

Following the hint given by the OP, it suffices to show that $$ \sum_{k=0}^n {n \choose k}^{\!2}=\sum_{k=0}^n {n \choose k}{n \choose {n-k}} = {2n \choose n}. $$ The last equality is a consequence of the following more general identity (known as Vandermonde's identity) $$ \sum_{j=0}^k \binom{n-m}{k-j}\binom{m}{j}=\binom{n}{k}, $$ where $n\ge m,k\ge 0$, which in turn is just an equality of the coefficients of $x^k$ is the left and right hand side of the binomial expansions of $$ (1+x)^{n-m}(1+x)^m=(1+x)^n. $$

$\endgroup$
5
$\begingroup$

Think of it this way.

On the right side, you're choosing $n$ objects from $2n$ objects.

On the left side, it's equal to $\sum\binom{n}{k}\binom{n}{n-k}$. So, divide the $2n$ objects into 2 groups, both of $n$ size. Then, the total number of way of choosing $n$ objects is partitioning over how many elements you choose from one group, and the remaining $n-k$ elements from the other group.

If we don't use the hint, we can consider the left side as still partitioning over picking $k$ objects from the first group, and then selecting $k$ elements not to choose from the second group, which would be $n-k$ elements you're choosing, so you still get $k$ elements in total.

$\endgroup$
2
$\begingroup$

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle #1 \right\rangle} \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left( #1 \right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \color{#00f}{\large\sum_{k = 0}^{n}{n \choose k}^{2}}&= \sum_{k = 0}^{n}{n \choose k}\ \overbrace{\int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{k + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{n \choose k}}= \int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z} \sum_{k = 0}^{n}{n \choose k}\pars{1 \over z}^{k}\,{\dd z \over 2\pi\ic} \\[3mm]&= \int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z} \,\pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} = \int_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} =\color{#00f}{\large{2n \choose n}} \end{align}

$\endgroup$
1
$\begingroup$

If we choose $k$ elements from a set with $n$ elements this is similar to don't choose $n-k$ elements from this set hence the number of subset with $k$ elements is equal to the number of subset with $n-k$ elements and this explain the given hint $${n\choose k}={n\choose n-k}$$

Now if we have two sets each one with $n$ elements and we choose $n$ elements: $k$ elements from the first and $n-k$ from the second set then the number of choice is $$\sum_{k=0}^n{n\choose k}{n\choose n-k}=\sum_{k=0}^n{n\choose k}{n\choose k}={2n\choose n}$$

$\endgroup$
1
$\begingroup$

Another way: Count the number of paths of length $2n$ on the integers taking $0$ to itself. Since there need to be $n$ lefts and $n$ rights, the total number is ${\displaystyle {2n \choose n}}$. The number of paths where the first $n$ moves contains $k$ rights and the second $n$ moves contains $n-k$ rights is ${\displaystyle {n \choose k}{n \choose n - k} = {n \choose k}^2}$. Adding this over all $k$ gives the identity.

$\endgroup$
1
$\begingroup$

Here is another way of doing it you just have to look at the binomial expansion of $(1+x)^n(1+\frac{1}{x})^n$ carefully:

$(1+x)^n(1+\frac{1}{x})^n = (^nC_0 + ^nC_1x + ^nC_2x^2 \cdots)(^nC_0 + ^nC_1\frac{1}{x} + ^nC_2\frac{1}{x^2} \cdots)$

you will find that $\sum_{k=0}^{n} (^nC_k)^2$ is actually the coefficient of $x^0$.

$$(1+x)^n(1+\frac{1}{x})^n = (1+x)^{2n}\frac{1}{x^n}$$ So the coefficient of $x^0$ in the expansion is $^{2n}C_n$, which proves the identity: $$\sum_{k=0}^{n} (^nC_k)^2 = ^{2n}C_n$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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