<s>[INST] Combinatorial proof of a binomial coefficient summation: $\sum_{k=1}^n \binom nk \binom n{k-1} = \frac12\binom{2n+2}{n+1} - \binom{2n}n$ Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that:
$$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$
I was told this is supposed to use a combinatorial proof and while I'm not that comfortable with that, many similar proofs use a mathematical proof that shows equality. Any guidance would be much appreciated.
 [/INST] Using standard binomial identities, this can be proven as follows:
$$
\begin{align}
\sum_{k=1}^n \binom{n}{k}\binom{n}{k-1}&=\sum_{k=1}^n \binom{n}{n-k}\binom{n}{k-1}\\
&=\binom{2n}{n-1}\\
&=\binom{2n+1}{n}-\binom{2n}{n}\\
&=\frac{n+1}{2n+2}\binom{2n+2}{n+1}-\binom{2n}{n}\\
&=\frac{1}{2}\binom{2n+2}{n+1}-\binom{2n}{n}
\end{align}
$$
Each identity can be given a simple combinatorial justification.
1.
$$
\binom{n}{k}=\binom{n}{n-k}
$$
The number of ways to choose $k$ items from $n$ is the number of ways to choose the complement of a set of $k$ items from $n$.
2.
$$
\sum_{k=1}^n \binom{n}{n-k}\binom{n}{k-1}=\binom{2n}{n-1}
$$
Given a set of green marbles, numbered $1...n$ and red marbles numbered $1...n$, count the choices of $n-1$ marbles from the aggregate $2n$ by counting the choices of $n-k$ green marbles and $k-1$ red marbles.
3.
$$
\binom{2n}{n-1}+\binom{2n}{n}=\binom{2n+1}{n}
$$
Given a set of green marbles numbered $1...2n$ and $1$ red marble, a choice $n$ marbles from the aggregate $2n+1$ either has the red marble, and thus $n-1$ of the $2n$ green marbles, or doesn't have the red marble, and thus $n$ of the $2n$ green marbles.
4.
$$
(2n+2)\binom{2n+1}{n}=(n+1)\binom{2n+2}{n+1}
$$
Putting $n+1$ marbles from a bag of $2n+2$ into a box and then choosing $1$ from the box is the same as choosing $1$ from the bag of $2n+2$ marbles and then putting $n$ of the remaining $2n+1$ marbles into the box.
</s>