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}$?

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}
$$
