# Asymptotic of a sum involving binomial coefficients

Could you help me to find an asymptotic for this sum?
$$\sum_{k=0}^{n – 1} (-1)^k {n \choose k} {3n – k – 1 \choose 2n – k} = {n \choose 0} {3n – 1 \choose 2n} – {n \choose 1} {3n – 2 \choose 2n – 1} + … + (-1)^{n-1} {n \choose n-1} {2n \choose n + 1}$$

I have tried to write binomials through factorials and work with it, but it seems like not right way to evaluate an asymptotic.

#### Solutions Collecting From Web of "Asymptotic of a sum involving binomial coefficients"

\begin{align} \sum_{k=0}^{n-1}(-1)^k\binom nk \color{blue}{\binom {3n-k-1}{2n-k}} &=\sum_{k=0}^{n-1}(-1)^k\binom nk\color{blue}{(-1)^{2n-k}\binom {-n}{2n-k}} \qquad&\color{blue}{\text{(upper negation)}}\\ &=\color{green}{\left[\sum_{k=0}^{n}\binom nk\binom {-n}{2n-k}\right]}-\color{orange}{\binom nk\binom {-n}{2n-k}\Biggr|_{k=n}}\\ &=\color{green}{\binom 0{2n}}-\color{orange}{\binom nn\binom {-n}{n}} \qquad&\color{green}{\text{(Vandermonde)}}\\ &=-\color{orange}{(-1)^n\binom{2n-1}n} \qquad&\color{orange}{\text{(upper negation)}}\\ &=(-1)^{n-1}\binom{2n-1}n=(-1)^{n-1}\binom{2n-1}{n-1}\quad\blacksquare \end{align}

Suppose we first seek to evaluate the somewhat more general

$$S_m(n) = \sum_{k=0}^n {n\choose k} (-1)^k {mn-k-1\choose 2n-k}$$

with $m$ an integer parameter.

Now introduce
$${mn-k-1\choose 2n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-k+1}} (1+z)^{mn-k-1} \; dz.$$

We thus get for the sum
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{mn-1}}{z^{2n+1}} \sum_{k=0}^n {n\choose k} (-1)^k \frac{z^k}{(1+z)^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{mn-1}}{z^{2n+1}} \left(1-\frac{z}{1+z}\right)^n\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{mn-n-1}}{z^{2n+1}} \; dz \\ = {mn-n-1\choose 2n}.$$

We see that this is zero when $m=2$ and $m=3$ and non-zero otherwise.

In the problem being asked we are computing
(the last term is not being included)
$$S_3(n) – (-1)^n {2n-1\choose n}$$

so we obtain
$$(-1)^{n+1} {2n-1\choose n}.$$

This can be treated with the asymptotic for the central binomial
coefficient. We get
$$(-1)^{n+1} \frac{n}{2n} {2n\choose n} = \frac{1}{2} (-1)^{n+1} {2n\choose n}.$$

The central binomial coefficient is
OEIS A000984
and is asymptotic to

$$\frac{4^n}{\sqrt{\pi n}}.$$

Hint: Use $\displaystyle{a-1\choose b}=(-1)^b~{b-a\choose b}$ in conjunction with Vandermonde’s identity. Also, notice

that the upper summation limit is $n-1$ instead of n.