<s>[INST] 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}
$.
 [/INST] 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
</s>