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}$ 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}
$.
 A: 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} $$
A: 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
A: 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.

A: 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}.$$
A: 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.
A: 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}$$
A: 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.


*

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

*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}
$$
A: $\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}
