Strange combinatorial identity $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0$ I need to find a combinatorial proof of this identity 
$$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0.$$
I think inclusion exclusion is the best method here. But I"m having a really hard time coming up with a set to count. Permutations don't work here. 
A hint would be really nice. Thanks. 
 A: Here is a proof using generating functions, quite a nice exercise in manipulation thereof. Rewrite the sum as follows:
$$\sum_{k=0}^n {n\choose k} (-1)^k {2(n-k)\choose n-1}.$$
Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the product of the two generating functions is the generating function of
$$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
Now clearly we have in the present case that
$$A(z) = \sum_{q\ge 0} (-1)^q \frac{z^q}{q!} = \exp(-z).$$
For $B(z)$ we get that
$$B_n(z) = \sum_{q\ge 0} {2q\choose n-1}  \frac{z^q}{q!}$$
where $B_1(z) = \exp(z).$
In order to investigate the $B_n(z)$ we introduce the bivariate generating function
$$Q(z,w) = \sum_{n\ge 1} B_n(z) w^n
= \sum_{n\ge 1} w^n  \sum_{q\ge 0} {2q\choose n-1}  \frac{z^q}{q!}
=  \sum_{q\ge 0}  \frac{z^q}{q!} \sum_{n\ge 1} w^n {2q\choose n-1} 
\\ = w \sum_{q\ge 0}  \frac{z^q}{q!} \sum_{n\ge 1} {2q\choose n-1} w^{n-1} 
=  w \sum_{q\ge 0}  \frac{z^q}{q!} (w+1)^{2q} 
\\ = w \exp(z (w+1)^2) = \exp(z) \times w \times \exp(z (w^2+2w)).$$
Extracting coefficients from this we find that
$$B_n(z) = [w^n] Q(z, w)
= \exp(z) [w^{n-1}] \exp(z (w^2+2w))
\\= \exp(z) [w^{n-1}] \exp(z w^2) \exp(2 z w)
= \exp(z) \sum_{a+2b=n-1} \frac{2^a z^a}{a!} \frac{z^b}{b!}.$$
This yields the formula
$$B_n(z) = \exp(z) 
\sum_{b=0}^{\lfloor (n-1)/2 \rfloor} 
\frac{2^{n-1-2b}}{(n-1-2b)! \times b!} z^{n-1-b}.$$
The value of our sum is therefore
$$n! [z^n] A(z) B_n(z) =
n! [z^n] \sum_{b=0}^{\lfloor (n-1)/2 \rfloor} .
\frac{2^{n-1-2b}}{(n-1-2b)! \times b!} z^{n-1-b} = 0$$
i.e. zero because as is easily seen the degree of the polynomial term is $n-1 < n.$
There is another calculation of this type at this MSE link -- I and at this MSE link -- II.
A: You have $n$ different pairs of shoes. How many ways are there to choose $n-1$ shoes so that you get at least one shoe from each pair? Obviously the answer is $0$, but you can also use inclusion-exclusion to count it the hard way as follows.
There are $\binom{2n}{n-1}$ ways to choose $n-1$ shoes. From this we want to exclude the ways that don’t include a shoe from the first pair; clearly there are $\binom{2n-2}{n-1}$ of those. We want to do the same for each of the $n$ pairs, so we should subtract $n\binom{2n-2}{n-1}$. But now each $(n-1)$-set that contains no shoe from either of the first two pairs has been counted once in $\binom{2n}{n-1}$ and subtracted twice in $n\binom{2n-2}{n-1}$ and should therefore be added back in. There are $\binom{2n-4}{n-1}$ such $(n-1)$-sets, and the same is true for each pair of the $\binom{n}2$ pairs of pairs, so we should add $\binom{n}2\binom{2n-4}{n-1}$.
Continuing in this fashion, we see that there are
$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{2n-2k}{n-1}$$
sets of $n-1$ shoes that meet the requirements, so
$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{2n-2k}{n-1}=0\;.$$
A: Let $\{S_{i}\}_{i=1}^{n}$ be a collection of sets each of size $2$. Double count sets $T$ of size $n-1$ from $\cup S_{i}$ such that $T$ contains an element from each $S_{i}$. THe RHS is clear. There are $n$ sets and $T$ has $n-1$ things this can never happen. The LHS use PIE. 
