Evaluation of a sum of $(-1)^{k} {n \choose k} {2n-2k \choose n+1}$ I have some question about the paper of which name is Spanning trees: Let me count the ways. The question concerns about  $\sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} 
{n \choose k} {2n-2k \choose n+1}$. Could you recommend me how to prove $\displaystyle \sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} {n \choose k} {2n-2k \choose n+1}=n 2^{n-1}$?
 A: Given a set of $2n$ objects arranged in pairs,
$$S=\{\,a_1,b_1,a_2,b_2,\ldots,a_n,b_n\}\ ,$$
we wish to choose $n-1$ objects in such a way that no two of them come from the same pair.
Method 1: choose the "missing" pair, then one element from each other.  This can be done in $n2^{n-1}$ ways.
Method 2: inclusion/exclusion.  The total way to choose $n-1$ elements from $S$ is
$$\binom{2n}{n-1}=\binom{2n}{n+1}\ .$$
The number of ways in which $k$ specific pairs are chosen is
$$\binom{2n-2k}{n-1-2k}=\binom{2n-2k}{n+1}\ .$$
So by inclusion/exclusion, the total number of ways is
$$\sum_{k=0}^K (-1)^k\binom{n}{k}\binom{2n-2k}{n+1}\ ,$$
where $K$ is the maximum number of pairs which can be chosen.  Since we are choosing $n-1$ elements altogether, $K=\lfloor(n-1)/2\rfloor$.
A: Since $\binom{m-2k}{n+1}$ is a degree $n+1$ polynomial in $k$ with lead term $\frac{(-2k)^{n+1}}{(n+1)!}$, we get that the multiple forward difference $\Delta_k^{n+1}\binom{m-2k}{n+1}=(-2)^{n+1}$. Multiply both sides by $(-1)^{n+1}$ to get
$$
\begin{align}
2^{n+1}
&=\sum_{k=0}^{n+1}(-1)^k\binom{n+1}{k}\binom{m-2k}{n+1}\\
&=\sum_{k=0}^{n+1}(-1)^k\left[\binom{n}{k}+\binom{n}{k-1}\right]\binom{m-2k}{n+1}\\
&=\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m-2k}{n+1}-\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m-2k-2}{n+1}\tag{1}
\end{align}
$$
Equation $(1)$ also says that for some $m_0$,
$$
\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m-2k}{n+1}=2^n(m-m_0)\tag{2}
$$
To determine $m_0$, consider the equation
$$
\begin{align}
\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m-2k}{n+1}
&=\sum_{k=0}^n(-1)^{n+1-k}\binom{n}{k}\binom{n-m+2k}{n+1}\\
&=\sum_{k=0}^n(-1)^{k+1}\binom{n}{k}\binom{3n-m-2k}{n+1}\tag{3}
\end{align}
$$
If we set $m=\frac32n$, then the left and right sides of $(3)$ are negatives of each other yet equal, therefore, $0$. Thus, $m_0=\frac32n$. Therefore,
$$
\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m-2k}{n+1}=2^n\left(m-\tfrac32n\right)\tag{4}
$$
Plugging $m=2n$ into $(4)$ and noting that $2n-2k\ge n+1\implies k\le\frac{n-1}{2}$, we get
$$
\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^n\binom{n}{k}\binom{2n-2k}{n+1}=n2^{n-1}\tag{5}
$$
A: Suppose we seek to evaluate
$$\sum_{k=0}^n {n\choose k}(-1)^k {2n-2k\choose n+1}.$$
Start from
$${2n-2k\choose n+1}
= \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{1}{z^{n+2}} (1+z)^{2n-2k} dz.$$
This yields the following expression for the sum
$$\frac{1}{2\pi i} 
\int_{|z|=\epsilon}
\sum_{k=0}^n {n\choose k} (-1)^k
\frac{1}{z^{n+2}} (1+z)^{2n-2k}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}  \frac{(1+z)^{2n}}{z^{n+2}}
\sum_{k=0}^n {n\choose k} (-1)^k
 (1+z)^{-2k}\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}  \frac{(1+z)^{2n}}{z^{n+2}}
\left(1-\frac{1}{(1+z)^2}\right)^n\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}  \frac{1}{z^{n+2}}
\left(2z+z^2\right)^n\; dz.$$
It follows that the sum is given by
$$[z^{n+1}] \left(2z+z^2\right)^n
= [z^1] (2+z)^n = {n\choose 1} 2^{n-1} = n 2^{n-1}.$$
A trace as to when this method appeared on MSE and by whom starts at this
MSE link.
