Show for $n$, $k$ $\in$ N, such that 1 $\leq k \leq n$, $\sum_{k = 1}^{n}\binom{n}{k}\binom{n}{k-1} = \frac{1}{2}\binom{2n+2}{n+1} - \binom{2n}{n}$ We are given a hint to show that both sides are equal to $\binom{2n}{n+1}$
For the right side, I have computed that
$$\frac{1}{2}\binom{2n+2}{n+1} - \binom{2n}{n}$$
$$=> \frac{(2n+2)!}{2((n+1)!)^2} - \frac{(2n)!}{n!^2}$$
$$=> \frac{(2n)!}{n!^2} * \left [  \frac{(2n+2)(2n+1)}{2(n+1)(n+1)} - 1\right ]$$
$$=> \frac{2n!}{(n!)^2}\left [ \frac{2n+1}{n+1} - \frac{n+1}{n+1}\right ]$$
$$=> \frac{2n!}{(n!)^2} * \frac{n}{n+1}$$
$$=> \frac{2n!}{n(n-1)!n!} * \frac{n}{n+1}$$
$$=> \frac{2n!}{n!(n+1)(n-1)!}$$
$$=> \frac{2n!}{(n-1)!(n+1)!}$$
$$=> \binom{2n}{n+1}$$
However, the left side is really giving me some trouble. I am not sure how to deal with the summation. Any help would be appreciated.

We have
$$\sum_{k=1}^n {n\choose k} {n\choose n+1-k}
= [z^{n+1}] (1+z)^n \sum_{k=1}^n {n\choose k} z^k
\\ = [z^{n+1}] (1+z)^n \sum_{k=0}^n {n\choose k} z^k
= [z^{n+1}] (1+z)^n (1+z)^n
= [z^{n+1}] (1+z)^{2n}
\\ = {2n\choose n+1}.$$
