Prove $\sum_{k=1}^{n}{n \choose k}{n \choose k-1} = {2n+2 \choose n+1}/2-{2n \choose n}$ I'm not sure where to start on this one. Would solving it via a combinatorial proof or induction be easier?
$\sum_{k=1}^{n}{n \choose k}{n \choose k-1} = {2n+2 \choose n+1}/2-{2n \choose n}$
 A: I'm not going to be incredibly rigorous about this right now because of lack of time, but I think I have a combinatoric intuition for this identity.
I'll give the proof first for brevity, then the intuition later.
First a lemma about the rhs. I will just state it but you can verify this with some basic arithmetic and simplification. 
Lemma 1:
$$
{2n+2 \choose n+1}/2-{2n \choose n} = {2n \choose n+1}
$$
Also note that 
$$
{2n \choose n+1} = \sum_{k=1}^{n}{n \choose k}{n \choose n-k+1} 
$$
This is essentially saying, if you partition your $2n$ objects into two colors with $n$ objects of one color and $n$ of the other, then picking $n+1$ objects is the sum of ways of picking $k$ things of one color and $n-k+1$ things from the other color for $k = 1$ to $k = n$.
Notice also that ${n \choose n-k+1} = {n \choose k-1}$ from the symmetry of the choose function, pascal's triangle, or what have you, so we have 
$$
\begin{align}
{2n \choose n+1} &= \sum_{k=1}^{n}{n \choose k}{n \choose n-k+1} \\
                 &= \sum_{k=1}^{n}{n \choose k}{n \choose k-1}
\end{align}
$$
as required. 

Intuition

Let us first understand what the LHS means combinatorially:

We have 
$$
\sum_{k=1}^{n}{n \choose k}{n \choose k-1} = {n \choose 1}{n \choose 0} + {n \choose 2}{n \choose 1} + {n \choose 3}{n \choose 2} + \ldots {n \choose n}{n \choose n-1}
$$
I view this as, given two bins with $n$ distinct objects in each, how many ways can you select one more thing from Bin A than from Bin B. So the total number of selections you could make are $1$ thing from Bin A and $0$ from Bin 2, which is ${n \choose 1}{n \choose 0}$, plus $2$ things from Bin A and $1$ thing from Bin B, which is ${n \choose 2}{n \choose 1}$ and so on. Essentially this is what the LHS is computing.

As for the RHS:

We can imagine combining Bin A and Bin B's objects into one big bin called Bin AB with $2n$ distinct objects, and seeing how many ways we can select $n+1$ things from them. Now the question is, how can this be viewed in terms of the LHS? First notice that the ways of selecting $n+1$ objects from Bin AB is the sum of the ways you can select 1 object of A and $n$ objects of B, plus the ways you can select 2 objects of A and $n-1$ objects of B, and so on. Essentially giving: $ \sum_{k=1}^{n}{n \choose k}{n \choose n-k+1}$. The final step is to notice that ${n \choose n-k+1}  = {n \choose k-1}$ and this is what finally connects the RHS to the LHS.
A: HINT: $\sum_k\binom{n}k\binom{n}{k-1}=\sum_k\binom{n}{n-k}\binom{n}{k-1}$; now apply Vandermonde's identity and simplify $\frac{1}2\binom{2n+2}{n+1}-\binom{2n}n$ to match.
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \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}$


*

*First Approach:
\begin{align}
&\sum_{k = 1}^{n}{n \choose k}{n \choose k - 1} =
{1 \over 2}\sum_{k = 1}^{n}\
\overbrace{\bracks{{n \choose k} + {n \choose k - 1}}^{2}}
^{\ds{{n + 1 \choose k}^{2}}}\ -\
{1 \over 2}\sum_{k = 1}^{n}{n \choose k}^{2} -
{1 \over 2}\sum_{k = 1}^{n}{n \choose k - 1}^{2}
\\[5mm] = &\
\bracks{-\,{1 \over 2} + {1 \over 2}\sum_{k = 0}^{n + 1}{n + 1 \choose k}^{2} - {1 \over 2}} -
\bracks{-\,{1 \over 2} + {1 \over 2}\sum_{k = 0}^{n}{n \choose k}^{2}} -
\bracks{{1 \over 2}\sum_{k = 0}^{n}{n \choose k}^{2} - {1 \over 2}}
\\[5mm] = &\
{1 \over 2}{2n + 2 \choose n + 1} - {2n \choose n}
\end{align}


where we used the well known identity
  $\ds{\sum_{j = 0}^{m}{m \choose j}^{2} = {2m \choose m}}$.


*Second Approach:
\begin{align}
\sum_{k = 1}^{n}{n \choose k}{n \choose k - 1} & =
\sum_{k = 1}^{n}{n \choose k}{n \choose n - k + 1} =
\sum_{k = 1}^{n}{n \choose k}\
\overbrace{\oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n - k + 2}}
\,{\dd z \over 2\pi\ic}}^{\ds{{n \choose n - k + 1}}}
\\[5mm] & =
\oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n + 2}}
\sum_{k = 1}^{n}{n \choose k}z^{k}\,{\dd z \over 2\pi\ic} =
\oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n + 2}}
\bracks{\pars{1 + z}^{n} - 1}\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\underbrace{\oint_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z^{n + 2}}\,{\dd z \over 2\pi\ic}}_{\ds{2n \choose n + 1}}\ -\ \underbrace{%
\oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n + 2}}\,{\dd z \over 2\pi\ic}}
_{\ds{n \choose n + 1} = 0} =\
\bbox[#ffe,10px,border:2px dotted navy]{\ds{2n \choose n + 1}}
\end{align}


Note that
  $\ds{{2n \choose n +1} = {\ds{2n + 2 \choose n + 1} \over 2} - {2n \choose n}}$.

