An alternating sum with binomial coefficients How to calculate this sum
$$
\sum_{k=0}^{n-1}(-1)^k{n \choose k} {3n-k-1 \choose 2n -k }
$$
without complex integral technique? Or how to calculate asymptotic nature this sum without calculation of this sum?
 A: I like combinatorial solutions, and the form of the sum
$$\sum_{k=0}^{n-1}(-1)^k\binom{n}k\binom{3n-k-1}{2n-k}$$
immediately suggests that it could result from an inclusion-exclusion calculation, though it is missing what would normally be the final term, 
$$(-1)^n\binom{2n-1}n\;.$$
It turns out to be convenient to make use of the fact that
$$\binom{3n-k-1}{2n-k}=\binom{3n-k-1}{n-1}$$
to rewrite the summation as
$$\sum_{k=0}^{n-1}(-1)^k\binom{n}k\binom{3n-k-1}{n-1}\;.$$
Suppose that I want to count the $(n-1)$-element subsets of $[3n-1]\setminus[n]$, where as usual $[m]=\{1,\ldots,m\}$ for any $m\in\Bbb Z^+$. For each $k\in[n]$ let $\mathscr{A}_k$ be the family of $(n-1)$-element subsets of $[3n-1]$ that do not contain $k$. It’s not hard to see that if $\varnothing\ne I\subseteq[n]$, then
$$\left|\bigcap_{k\in I}\mathscr{A}_k\right|=\binom{3n-1-|I|}{n-1}\;,$$
so
$$\left|\bigcup_{k\in[n]}\mathscr{A}_k\right|=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{k\in I}\mathscr{A}_k\right|=\sum_{k=1}^n(-1)^{k+1}\binom{n}k\binom{3n-1-k}{n-1}\;.$$
This is the number of $(n-1)$-element subsets $S$ of $[3n-1]$ such that $[n]\nsubseteq S$, so
$$\begin{align*}
\binom{3n-1}{n-1}-\sum_{k=1}^n(-1)^{k+1}\binom{n}k\binom{3n-1-k}{n-1}&=\binom{3n-1}{n-1}+\sum_{k=1}^n(-1)^k\binom{n}k\binom{3n-1-k}{n-1}\\
&=\sum_{k=0}^n(-1)^k\binom{n}k\binom{3n-1-k}{n-1}
\end{align*}$$
is the number of $(n-1)$-element subsets $S$ of $[3n-1]$ such that $[n]\subseteq S$. This is obviously $0$, so
$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{3n-1-k}{n-1}=0\;,$$
and
$$\begin{align*}
\sum_{k=0}^{n-1}(-1)^k\binom{n}k\binom{3n-1-k}{n-1}&=-(-1)^n\binom{2n-1}{n-1}\\
&=(-1)^{n+1}\binom{2n-1}{n-1}\\
&=(-1)^{n+1}\binom{2n-1}n\;.
\end{align*}$$
A: It is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g.
 \begin{align*}
 [z^k](1+z)^n=\binom{n}{k}
 \end{align*}

We obtain for $n\geq 1$:
  \begin{align*}
 \sum_{k=0}^{n-1}&(-1)^k\binom{n}{k}\binom{3n-k-1}{2n-k}\\
 &=\sum_{k=0}^{n}\binom{n}{k}\binom{-n}{2n-k}-\binom{-n}{n}\tag{1}\\
 &=\sum_{k=0}^\infty[z^k](1+z)^n[u^{2n-k}](1+u)^{-n}+\color{blue}{(-1)^{n-1}\binom{2n-1}{n}}\tag{2}\\
 &=[u^{2n}](1+u)^{-n}\sum_{k=0}^\infty u^k[z^k](1+z)^n+(-1)^{n-1}\binom{2n-1}{n}\tag{3}\\
 &=[u^{2n}]1+(-1)^{n-1}\binom{2n-1}{n}\tag{4}\\
 &=(-1)^{n-1}\binom{2n-1}{n}
 \end{align*}

Comment:


*

*In (1) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^k$. We also add the term with index $k=n$ to the sum and subtract $\binom{-n}{n}$ accordingly.

*In (2) we apply the coefficient of operator twice and use again the binomial identity as in (1). We also set the upper limit of the sum to $\infty$ without changing anything since we are adding zeros only.
In fact we have isolated the result (blue) and show the rest is equal to zero.

*In (3) we use the linearity of the coefficient of operator and apply the rule
$$[z^{p-q}]A(z)=[z^p]z^qA(z)$$

*In (4) we use the substitution rule with $z:=u$
\begin{align*}
A(u)=\sum_{k=0}^\infty a_k u^k=\sum_{k=0}^\infty u^k [z^k]A(z)
\end{align*}
do some simplifications and observe the coefficient of $[u^{2n}]1=0$.
A: $(-1)^k\binom{n}{k}$ is the coefficient of $x^k$ in $(1-x)^n$.
$\binom{3n-k-1}{2n-k}=\binom{3n-k-1}{n-1}$ is the coefficient of $x^{2n-k}$ in
$$ \sum_{h\geq 0}\binom{n-1+h}{n-1}x^h = \frac{1}{(1-x)^n} $$
It follows that for any $n>0$
$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{3n-k-1}{n-1}=[x^{2n}]\frac{(1-x)^n}{(1-x)^n} = 0 $$
and:
$$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}\binom{3n-k-1}{n-1}= \color{red}{-(-1)^{n}\binom{n}{n}\binom{2n-1}{n-1}}. $$
Asymptotics can be derived from $\binom{2n}{n}\approx\frac{4^n}{\sqrt{\pi n}}.$
A: Ok here we go:
$$
s(k,n)=(-1)^k\binom{n}{k}\binom{3n-k-1}{2n-k}=
(-1)^k\binom{n}{k}\binom{-(-n)+ 2n-k-1}{2n-k}=\binom{n}{k}\binom{-n}{2n-k}
$$
See here
Furthermore in the form above it is clear that
$$
\sum_{n=0}^{2n}s(k,n)=0 \quad \color{red}{(1)}
$$
by Vandermonde's identiy. 
Furthermore 
$$s(k,n)=0 \quad \text{for} \quad  k>n  \quad \color{blue}{(2)} $$
by definition of the Binomial coefficent.
Combining $\color{red}{(1)}$ and $\color{blue}{(2)}$ yields
$$
\sum_{n=0}^{n-1}s(k,n)=-s(n,n) 
$$
or

$$
\sum_{n=0}^{n-1}s(k,n)=-\binom{-n}{n}
$$

A: $$
\begin{align}
\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}\binom{3n-k-1}{2n-k}
&=(-1)^{n+1}\binom{2n-1}{n}+\sum_{k=0}^n\binom{n}{k}\binom{-n}{2n-k}\tag{1}\\
&=(-1)^{n+1}\binom{2n-1}{n}+\binom{0}{2n}\tag{2}\\[4pt]
&=(-1)^{n+1}\binom{2n-1}{n}+[n=0]\tag{3}
\end{align}
$$
Explanation:
$(1)$: add and subtract the $k=n$ term
$\phantom{(1)\text{:}}$ use negative binomial coefficients to get $(-1)^k\binom{3n-k-1}{2n-k}=\binom{-n}{2n-k}$
$(2)$: Vandermonde's Identity
$(3)$: $\binom{0}{2n}=[n=0]$ using Iverson Brackets
A: I wrote a python script to compute the first few values of the sequence:
$n$: $f(n)$
2: -3
3: 10
4: -35
5: 126
6: -462
7: 1716
8: -6435
9: 24310
10: -92378
11: 352716
12: -1352078
13: 5200300
14: -20058300
15: 77558760
16: -300540195
17: 1166803110
18: -4537567650
19: 17672631900
I inputted the first 10 of those values into the OEIS and found that your sum appears to be:
$$(-1)^{n-1}\binom{2n-1}{n} = \sum_{k=0}^{n-1}(-1)^k\binom{n}{k}\binom{3n-k-1}{2n-k}$$
The LHS below should be much easier to analyze asymptotically (use Stirling's approximation).  The two sequences match on at least the first 20 or so terms (all I checked).  You may want to prove (induction perhaps) that they are the same--unless you believe/are convinced enough that 20+ term match implies they are the same already.
