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

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.
