Evaluate sum using generating function

Question

I'm trying to evaluate this sum:

$$ \sum\limits_{s = 0}^{500} (-1)^s \binom{3000 - 2s}{2000} \binom{2001}{s}$$

As I think we need to use an expansion of $(1 -x)^n (1+x)^k$, but I've tried several times, using different powers but stuck every time.

Could you help me, please?

Answer 1

Note: Please note, this is essentially the same as Marko Riedels answer. Here we simply avoid the integral notation which might be somewhat more convenient.

In order to calculate OPs sum it's beneficial to consider the more general expression

\begin{align*} S_n=\sum_{s= 0}^{\lfloor\frac{n}{2}\rfloor}(-1)^s\binom{3n-2s}{2n}\binom{2n+1}{s} \end{align*}

We obtain OPs expression by setting $n=1000$. We need one additional small step before we start calculating $S_n$.

Since $\binom{m}{k}=\binom{m}{m-k}$ and $\binom{-m}{k}=\binom{m+k-1}{k}(-1)^k$ the following is valid \begin{align*} \binom{3n-2s}{2n}=\binom{3n-2s}{n-2s}=\binom{-(2n+1)}{n-2s}(-1)^n \end{align*}

So, we can rewrite $S_n$ as \begin{align*} S_n=(-1)^n\sum_{s= 0}^{\lfloor\frac{n}{2}\rfloor}(-1)^s\binom{-(2n+1)}{n-2s}\binom{2n+1}{s} \end{align*}

Observe the nice symmetry regarding $2n+1$. This will help simplifying $S_n$.

In the following we use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a polynomial or a series.

We obtain

\begin{align*} S_n&=(-1)^n\sum_{s= 0}^{\lfloor\frac{n}{2}\rfloor}(-1)^s\binom{-(2n+1)}{n-2s}\binom{2n+1}{s}\\ &=(-1)^n\sum_{s= 0}^{\lfloor\frac{n}{2}\rfloor}[x^{n-2s}](1+x)^{-(2n+1)}[y^s](1-y)^{2n+1}\tag{1}\\ &=(-1)^n[x^n](1+x)^{-(2n+1)}\sum_{s= 0}^{\lfloor\frac{n}{2}\rfloor}x^{2s}[y^s](1-y)^{2n+1}\tag{2}\\ &=(-1)^n[x^n](1+x)^{-(2n+1)}(1-x^2)^{2n+1}\tag{3}\\ &=(-1)^n[x^n](1-x)^{2n+1}\tag{4}\\ &=\binom{2n+1}{n} \end{align*}

Comment:

• In (1) we write the binomial coefficients as coefficients of polynomials (resp. series) $\binom{m}{k}=[x^k](1+x)^m$. Note, that the factor $(-1)^s$ is respected in $[y^s](1-y)^{2n+1}$.

• In (2) we see that the representation as coefficients of polynomials is convenient, since we can put parts of the expression, which do not depend on $s$ outside the sum. We also use the rule $$[x^{n+m}]p(x)=[x^n]x^{-m}p(x)$$

• In (3) we use the substitution rule (see also (1)): \begin{align*} (1-x^2)^{2n+1}&=\sum_{s\geq 0}\binom{2n+1}{s}(-1)^sx^{2s}\\ &=\sum_{s\geq 0}x^{2s}[y^s](1-y)^{2n+1} \end{align*}

• In (4) we use the symmetry regarding $2n+1$ which helps cancelling a factor of $(1-x^2)^{2n+1}=(1-x)^{2n+1}(1+x)^{2n+1}$

Since OPs expression is $S_{1000}$ we finally conclude \begin{align*} S_{1000}&=\sum_{s=0}^{500}(-1)^s\binom{3000-2s}{2000}\binom{2001}{s}\\ &=[x^{1000}](1+x)^{2001}\\ &=\binom{2001}{1000} \end{align*}

Answer 2

Suppose we seek to evaluate $$S_n = \sum_{q=0}^n (-1)^q {6n-2q\choose 4n} {4n+1\choose q}.$$

Introduce $${6n-2q\choose 4n} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n-2q+1}} \frac{1}{(1-z)^{4n+1}} \; dw.$$

This is zero when $q\gt n$ so we may extend the summation to infinity to obtain $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n+1}} \frac{1}{(1-w)^{4n+1}} \sum_{q\ge 0} (-1)^q {4n+1\choose q} w^{2q} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n+1}} \frac{1}{(1-w)^{4n+1}} (1-w^2)^{4n+1}\; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n+1}} (1+w)^{4n+1}\; dw.$$

This evaluates to $${4n+1\choose 2n}$$ by inspection.

The desired value is given by $S_{500}.$