binomials product alternating sum calculation I need to somehow prove that $\sum\limits_{k = 0}^{n - 1} {n \choose k} {3 n - k - 1 \choose 2 n - k}(-1)^k = (-1)^{n + 1} {2 n - 1 \choose n}$.
I didn't manage to do it using induction or any combinatorial ideas. Could someone help me?
 A: $$
\begin{align}
\sum_{k=0}^{n-1}\binom{n}{k}\binom{3n-k-1}{2n-k}(-1)^k
&=\sum_{k=0}^n\binom{n}{k}\binom{-n}{2n-k}-\binom{n}{n}\binom{-n}{n}\tag{1}\\
&=\binom{0}{2n}-\binom{-n}{n}\tag{2}\\
&=[n=0]-(-1)^n\binom{2n-1}{n}\tag{3}
\end{align}
$$
Explanation:
$(1)$: $(-1)^k\binom{3n-k-1}{2n-k}=\binom{-n}{2n-k}$. See this answer.
$(2)$: Vandermonde's Identity
$(3)$: $\binom{-n}{n}=(-1)^n\binom{2n-1}{n}$. See this answer.
A: We have that
$$ S(n)=\sum_{k=0}^{n}\binom{n}{k}\binom{3n-k-1}{2n-k}(-1)^k \tag{1}$$
is the coefficient of $x^{2n}$ in the product between:
$$ A(x) = \sum_{k=0}^{n}\binom{n}{k}x^k(-1)^k\quad\text{and}\quad B(x)=\sum_{k=n}^{2n}\binom{n+k-1}{k}x^k. \tag{2}$$
Since:
$$ \widetilde{B}(x) = \sum_{k\geq 0}\binom{n+k-1}{k}x^k = \frac{1}{(1-x)^n}\tag{3}$$
we have:
$$ S(n) = [x^{2n}]\left( A(x)\cdot\widetilde{B}(x)\right) = [x^{2n}]\left((1-x)^n\cdot \frac{1}{(1-x)^n}\right) = 0\tag{4} $$
for every $n>0$, hence:

$$ \sum_{k=0}^{n-1}\binom{n}{k}\binom{3n-k-1}{2n-k}(-1)^k = 0-\binom{n}{n}\binom{3n-n-1}{2n-n}(-1)^n = (-1)^{n+1}\binom{2n-1}{n}.$$

A: Suppose we seek to verify that
$$\sum_{k=0}^{n-1} 
{n\choose k} {3n-k-1\choose 2n-k} (-1)^k
= (-1)^{n+1} {2n-1\choose n}$$
which is the same as
$$\sum_{k=0}^{n} 
{n\choose k} {3n-k-1\choose 2n-k} (-1)^k
= \left((-1)^n+(-1)^{n+1}\right) {2n-1\choose n} = 0.$$
Introduce
$${3n-k-1\choose 2n-k} = {3n-k-1\choose n-1} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n}} 
(1+z)^{3n-k-1} \; dz.$$

This yields for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n}} 
(1+z)^{3n-1} 
\sum_{k=0}^n {n\choose k} (-1)^k \frac{1}{(1+z)^k} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n}} 
(1+z)^{3n-1} \left(1-\frac{1}{1+z}\right)^n \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n}} 
(1+z)^{3n-1} \frac{z^n}{(1+z)^{n}} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
(1+z)^{2n-1} \; dz = 0.$$
A: First multiply both sides of the desired identity by $(-1)^{n-1}$ to get the equivalent identity
$$\sum_{k=0}^{n-1}(-1)^{n-1-k}\binom{n}k\binom{3n-k-1}{2n-k}=\binom{2n-1}n\;.$$
Subtracting $\binom{2n-1}n$ from both sides and multiplying by $(-1)^n$ yields the equivalent form
$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{3n-1-k}{2n-k}=0\;.\tag{1}$$
This has the look of an inclusion-exclusion calculation, and indeed it turns out to be interpretable as one.
We want to count the $2n$-element subsets of $[3n-1]$ that are disjoint from $[n]$. Of course $|[3n-1]\setminus[n]|=2n-1$, so there are no such subsets. On the other hand, for each $k$-element subset $S$ of $[n]$ there are $\binom{3n-1-k}{2n-k}$ $2n$-element subsets of $[3n-1]$ that contain $S$. By this special case of the inclusion-exclusion principle, the lefthand side of $(1)$ is the number of $2n$-element subsets of $[3n-1]$ that do not contain any $k\in[n]$.
