Simplify the sum $ \sum_{i=0}^{k}(-1)^i i \binom{n}{i} \binom{n}{k-i}$ How to deal with combinatoric interpretation (or just solving it in algebraic way) when we have $(-1)^i$ factor in our sum?

Example task: 
Simplify the sum:
$$ \sum_{i=0}^{k}(-1)^i i \binom{n}{i} \binom{n}{k-i} \text{ for } 0\le k \le n $$
For task without $(-1)^i$
$$ \sum_{i=0}^{k} i \binom{n}{i} \binom{n}{k-i} = n \binom{2 n-1}{k-1} $$
I can write that interpretation: 


*

*I have $n$ rabbits and $k$ slots

*Each rabbit can be in both slot of first type and second type

*slots of first type + second type = $k$

*Lets double rabbits

*I choose one rabbit as an king and it will be also a rabbit to slot of first type

*so I need to choose $2n-1$ rabbit for $k-1$ slots 
But I don't know how to deal with $(-1)^i$
 A: Darij Grinberg's answer cited a very nice combinatorial proof which I reproduce here for completeness. 
Let $[n]=\{1,2,\dots,n\}$. We provide a combinatorial interpretation for the form $$\sum_i (-1)^in\binom{n-1}{i-1}\binom{n}{k-i}$$ This is a signed count of ordered triples $(x,A,B)$, where $x\in [n], A\subseteq [n]\setminus \{x\},B\subseteq [n]$, and $|A|+|B|=k-1$. A triple is counted positively if $|A|$ is odd, and negatively otherwise. 
Given such a triple $(x,A,B)$, we define its partner $f(x,A,B)$ as follows. Find the largest element of  $(A\setminus B)\cup (B\setminus (A\cup \{x\}))$, and move it to the other set. If this set is empty, we leave $f$ undefined.
You can check that $f(f(x,A,B))=(x,A,B)$ whenever $f$ is defined, so that this is a well defined pairing operation. Furthermore, since $(x,A,B)$ and $f(x,A,B)$ have opposite signs, they cancel out each other in the summation, so they can be ignored. 
Therefore, the only triples which contribute to the count are those for which $f$ is undefined. The only triples for which $f$ is undefined are those of the form $(x,A,A)$ and $(x,A,A\cup \{x\})$. Only one of these forms is possible, depending on the parity of $k$, and you can check that in either case the number of triples is
$$
n\binom{n-1}{\lfloor(k-1)/2\rfloor}
$$
and each exceptional triple has sign $(-1)^{\lfloor(k-1)/2\rfloor + 1}$. 
A: Starting from
$$\sum_{q=0}^k (-1)^q q {n\choose q} {n\choose k-q}$$
we have
$$\sum_{q=1}^k (-1)^q q {n\choose q} {n\choose k-q}
= n \sum_{q=1}^k (-1)^q {n-1\choose q-1} {n\choose k-q}
\\ = n [z^k] (1+z)^n
\sum_{q=1}^k (-1)^q {n-1\choose q-1} z^q
\\ = - n [z^{k-1}] (1+z)^n
\sum_{q=1}^k (-1)^{q-1} {n-1\choose q-1} z^{q-1}.$$
Now  if $q\gt  k$ then  there is  no contribution  to the  coefficient
extractor:
$$- n [z^{k-1}] (1+z)^n
\sum_{q\ge 1} (-1)^{q-1} {n-1\choose q-1} z^{q-1}
\\ = - n [z^{k-1}] (1+z)^n (1-z)^{n-1}
= - n [z^{k-1}] (1+z) (1-z^2)^{n-1}
\\ = - n [z^{k-1}] (1-z^2)^{n-1}
- n [z^{k-2}] (1-z^2)^{n-1}.$$
If $k$ is odd this yields
$$-n (-1)^{(k-1)/2} {n-1\choose (k-1)/2}$$
and if it is even
$$-n (-1)^{(k-2)/2} {n-1\choose (k-2)/2}.$$
Join these to obtain
$$\bbox[5px,border:2px solid #00A000]{
(-1)^{1+\lfloor (k-1)/2 \rfloor} \times n \times
{n-1\choose \lfloor (k-1)/2 \rfloor}.}$$
