4
$\begingroup$

Show that $\sum_{k=0}^{n}\binom{n}{k}^2=\frac{n+1}{n}\sum_{k=1}^{n}\binom{n}{k}\binom{n}{k-1}$

I came across this result while trying to solve this:

inductive proof for $\binom{2n}{n}$

My proof is cumbersome, so I hope that someone can come up with a more elegant proof.

Note: I know that $\sum_{k=0}^{n}\binom{n}{k}^2 =\binom{2n}{n} $.

$\endgroup$
4
$\begingroup$

The fact that $$\sum_{k=0}^\infty {n \choose k}^2 = {2n \choose n}$$ has a combinatorial interpretation: to select $n$ items from $2n$, first take an arbitrary subset of the first $n$ items, and if this had cardinality $k$ select $n-k$ of the second $n$ items.

Similarly,

$$ {2n \choose n} = \sum_{k=1}^{n} {n+1 \choose k} {n-1 \choose n-k}$$

and $$ {n+1 \choose k} {n-1 \choose n-k} = \frac{n+1}{n} {n \choose k}{n \choose k-1} $$

$\endgroup$
1
  • $\begingroup$ Damn, you're good. $\endgroup$ – marty cohen Sep 29 '16 at 22:40
2
$\begingroup$

Vandermonde's Identity $$ \begin{align} \sum_{k=0}^n\binom{n}{k}^{\large2} &=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}\\ &=\binom{2n}{n} \end{align} $$ and $$ \begin{align} \sum_{k=1}^n\binom{n}{k}\binom{n}{k-1} &=\sum_{k=1}^n\binom{n}{k}\binom{n}{n-k+1}\\ &=\binom{2n}{n+1}\\ &=\frac{n}{n+1}\binom{2n}{n} \end{align} $$ which proves the result.


Another Approach Copied From This Answer

Lemma: $$ \sum_{k=1}^n\binom{n}{k}\binom{n}{k-1}=\frac{n}{n+1}\sum_{k=0}^n\binom{n}{k}^2\tag{1} $$ Proof:

Since $\binom{n}{k-1}=\frac{k}{n-k+1}\binom{n}{k}$, we have $\binom{n}{k}+\binom{n}{k-1}=\frac{n+1}{n-k+1}\binom{n}{k}$. Therefore, $$ \frac{n-k+1}{n+1}\left[\binom{n}{k}+\binom{n}{k-1}\right]\binom{n}{k-1}=\binom{n}{k}\binom{n}{k-1}\tag{2} $$ Since $\binom{n}{k}=\frac{n-k+1}{k}\binom{n}{k-1}$, we have $\binom{n}{k}+\binom{n}{k-1}=\frac{n+1}{k}\binom{n}{k-1}$. Therefore, $$ \frac{k}{n+1}\left[\binom{n}{k-1}+\binom{n}{k}\right]\binom{n}{k}=\binom{n}{k-1}\binom{n}{k}\tag{3} $$ Adding $(2)$ and $(3)$ and cancelling yields $$ \frac{n-k+1}{n+1}\binom{n}{k-1}^2+\frac{k}{n+1}\binom{n}{k}^2=\binom{n}{k-1}\binom{n}{k}\tag{4} $$ Summing $(4)$ over $k$, and substituting $k\mapsto k+1$ in the leftmost sum, gives $$ \frac{n}{n+1}\sum_{k=0}^n\binom{n}{k}^2=\sum_{k=1}^n\binom{n}{k-1}\binom{n}{k}\tag{5} $$ QED

$\endgroup$
1
  • $\begingroup$ My favorite out of the Vandermonde variants. Concise and complete. (+1) $\endgroup$ – Markus Scheuer Sep 30 '16 at 9:15
1
$\begingroup$

We can also use the integral representation of the binomial coefficient $$\dbinom{n}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{n}}{z^{k+1}}dz $$ and so $$\begin{align}\frac{n+1}{n}\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n}{k-1}= & \frac{n+1}{2n\pi i}\oint_{\left|z\right|=1}\left(1+z\right)^{n}\sum_{k=0}^{n}\dbinom{n}{k}z^{-k}dz \\ = & \frac{n+1}{2n\pi i}\oint_{\left|z\right|=1}\left(1+z\right)^{n}\left(1+1/z\right)^{n}dz \\ = & \frac{n+1}{2n\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{2n}}{z^{n}}dz \\ = & \frac{n+1}{n}\dbinom{2n}{n-1} \\ = & \color{red}{\dbinom{2n}{n}} \end{align} $$ as wanted, since we have the recurrence $$\frac{m+1-l}{l}\dbinom{m}{l-1}=\dbinom{m}{l}.$$ Using this technique, it is quite simple to show that $$\sum_{k=0}^{n}\dbinom{n}{k}^{2}=\dbinom{2n}{n}.$$

$\endgroup$
0
1
$\begingroup$

Here we show the binomial identity from scratch without using Vandermonde's identity. It is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \sum_{k=0}^n\binom{n}{k}^2&=\sum_{k=0}^\infty[z^k](1+z)^n[u^k](1+u)^n\tag{1}\\ &=[z^0](1+z)^n\sum_{k=0}^\infty z^{-k}[u^k](1+u)^n\tag{2}\\ &=[z^0](1+z)^n\left(1+\frac{1}{z}\right)^n\tag{3}\\ &=[z^n](1+z)^{2n}\\ &=\binom{2n}{n} \end{align*}

Comment:

  • In (1) we apply the coefficient of operator twice and set the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

  • In (2) we use the linearity of the coefficient of operator and apply the rule $$[z^{p+q}]A(z)=[z^p]z^{-q}A(z)$$

  • In (3) we use the substitution rule with $u:= \frac{1}{z}$

\begin{align*} A(u)=\sum_{n=0}^\infty a_n u^n=\sum_{n=0}^\infty u^n [z^n]A(z) \end{align*}

We obtain in the same way as above \begin{align*} \frac{n+1}{n}\sum_{k=1}^n\binom{n}{k}\binom{n}{k-1} &=\frac{n+1}{n}\sum_{k=1}^n\frac{n}{k}\binom{n-1}{k-1}\binom{n}{k-1}\\ &=\sum_{k=0}^{n-1}\binom{n-1}{k}\binom{n+1}{k+1}\\ &=\sum_{k=0}^\infty[z^k](1+z)^{n-1}[u^{k+1}](1+u)^{n+1}\\ &=[z^0](1+z)^{n-1}\sum_{k=0}^\infty z^{-k}[u^k]\frac{(1+u)^{n+1}}{u}\\ &=[z^0](1+z)^{n-1}\frac{\left(1+\frac{1}{z}\right)^{n+1}}{\frac{1}{z}}\\ &=[z^n](1+z)^{2n}\\ &=\binom{2n}{n} \end{align*} and the claim follows.

$\endgroup$
1
  • $\begingroup$ Nice work. (+1). The substitution rule always makes for an interesting effect. $\endgroup$ – Marko Riedel Sep 30 '16 at 20:52
0
$\begingroup$

I don't have a full answer, but I was thinking maybe this could be useful:

$2^{2n}=\left(\sum_{k=0}^n \binom{n}{k}\right)^2=\sum_{k=0}^n \binom{n}{k}^2+2e_2\left( \binom{n}{j} \right)$ where $e_2\left( x_j\right)$ is the elementary symmetric polynomial on the $n$ symbols $x_j$ for $j=1,...,n$ So that $\sum_{k=0}^n \binom{n}{k}^2=2^{2n}-2e_2\left( \binom{n}{j}\right)$

I will think about this some more to see if it leads anywhere.

$\endgroup$
1
  • $\begingroup$ This looks more like a comment than an answer to me. $\endgroup$ – Surb Sep 29 '16 at 21:40
0
$\begingroup$

Apply four equation: $$\sum_{k=0}^\infty\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n} [1]$$ and $$\binom{n}{k}=\frac{n}{n-k}\binom{n-1}{k} [2]$$ and $$\binom{n}{k}=\binom{n}{n-k} [3]$$ and (for k!= 0) $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1} [4]$$

Apply [1] and [2] we have: $$\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{n+n}{n}=\binom{2n}{n}$$ $$=\frac{2n}{2n-n}\binom{2n-1}{n}=2\binom{2n-1}{n}$$

Note that $\binom{n}{n+1}=0$, Apply [3] and [1] and [4] we have

$$\frac{n+1}{n}\sum_{k=1}^{n}\binom{n}{k}\binom{n}{k-1} = \frac{n+1}{n}\sum_{k=0}^{n+1}\binom{n}{k}\binom{n}{n+1-k}$$ $$ = \frac{n+1}{n}\binom{n+n}{n+1}=\frac{n+1}{n}\binom{2n}{n+1} $$ $$ = \frac{n+1}{n}\frac{2n}{n+1}\binom{2n-1}{n} = 2\binom{2n-1}{n}$$

Conclusion: $$\sum_{k=0}^{n}\binom{n}{k}^2=\frac{n+1}{n}\sum_{k=1}^{n}\binom{n}{k}\binom{n}{k-1} = 2\binom{2n-1}{n}$$

$\endgroup$
0
$\begingroup$

Elegant Proof

You have $2n$ students $n$ male, $n$ female. You want to construct a committee of $n$ students and you also want to make one of them president of the committee. You can do this in $$ n{2n \choose n} $$ different ways.

  1. Now say the number of male students are $k$. Then this is also equivalent to choosing $k$ male and $n-k$ female students and making one of them president $$ n \sum \limits_{k=0}^{n-1} {n \choose k} {n \choose n-k} $$

  2. Now lets first choose the non-president $n-1$ committee members then choose the president from the remaining $n+1$ You can do this in $$ (n+1) \sum \limits_{k=0}^{n} {n \choose k} {n \choose n-k+1} $$ different ways. Hence we have

$$ n \sum \limits_{k=0}^{n} {n \choose k} {n \choose n-k} = (n+1) \sum \limits_{k=0}^{n} {n \choose k} {n \choose n-1-k} $$ which is same as $$ n \sum \limits_{k=0}^{n} {n \choose k}^2 = (n+1) \sum \limits_{k=0}^{n} {n \choose k} {n \choose k+1} $$

$\endgroup$
0
$\begingroup$

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{k = 0}^{n}{n \choose k}^{2} = {n + 1 \over n}\sum_{k = 1}^{n}{n \choose k}{n \choose k - 1}:\ ?}$.

\begin{align} &\color{#f00}{{n + 1 \over n}\sum_{k = 1}^{n}{n \choose k}{n \choose k - 1}} = {n + 1 \over 2n}\sum_{k = 1}^{n}\braces{% \bracks{{n \choose k} + {n \choose k - 1}}^{2} - {n \choose k}^{2} - {n \choose k - 1}^{2}} \\[5mm] = &\ {n + 1 \over 2n}\sum_{k = 1}^{n}{n + 1 \choose k}^{2} - {n + 1 \over 2n}\sum_{k = 1}^{n}{n \choose k}^{2} - {n + 1 \over 2n}\sum_{k = 1}^{n}{n \choose k - 1}^{2} \quad\pars{\begin{array}{l}Pascal\ Triangle\ Identity\ \\ \mbox{in the first term}\end{array}} \\[5mm] = &\ {n + 1 \over 2n}\bracks{-1 + \sum_{k = 0}^{n + 1}{n + 1 \choose k}^{2} - 1} - {n + 1 \over 2n}\bracks{-1 + \sum_{k = 0}^{n}{n \choose k}^{2}} - {n + 1 \over 2n}\bracks{\sum_{k = 0}^{n}{n \choose k}^{2} - 1} \\[5mm] = &\ \color{#f00}{{n + 1 \over 2n}\sum_{k = 0}^{n + 1}{n + 1 \choose k}^{2} - {n + 1 \over n}\sum_{k = 0}^{n}{n \choose k}^{2}}\label{1}\tag{1} \end{align}

\begin{equation} \mbox{We'll use the}\ well\ known\ identity\quad \sum_{j = 0}^{m}{m \choose j}^{2} = {2m \choose m}\label{2}\tag{2} \end{equation}


Expression \eqref{1} becomes: \begin{align} &\color{#f00}{{n + 1 \over n}\sum_{k = 1}^{n}{n \choose k}{n \choose k - 1}} = {n + 1 \over 2n}{2n + 2 \choose n + 1} - {n + 1 \over n}\sum_{k = 0}^{n}{n \choose k}^{2} \\[5mm] = &\ {n + 1 \over 2n}\bracks{{\pars{2n + 2}\pars{2n + 1} \over \pars{n + 1}\pars{n + 1}}{2n \choose n}} - {n + 1 \over n}\sum_{k = 0}^{n}{n \choose k}^{2} = {2n + 1 \over n}\ \overbrace{\sum_{k = 0}^{n}{n \choose k}^{2}} ^{\ds{\mbox{see}\ \eqref{2}}}\ -\ {n + 1 \over n}\sum_{k = 0}^{n}{n \choose k}^{2} \\[5mm] = &\ \color{#f00}{\sum_{k = 0}^{n}{n \choose k}^{2}} \end{align}

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