# A sum of products of binomial coefficients

I am looking for a proof or a reference for the following ( apparent ) combinatorial identity:

$$\sum_{i = s}^{s+t}\left(\,{-1}\,\right)^{\, i}{i \choose s} {s \choose i - t} = \left(\,{-1}\,\right)^{s + t},\quad\mbox{where}\ s\geq t\geq 0\ \mbox{are integers}$$

Any help will be appreciated.

• This is one of many identities that boil down to Chu-Vandermonde convolution after a sequence of transformations (using symmetry and upper negation). To wit: Replace $\dbinom{i}{s}$ by $\dbinom{i}{i-s}$ and apply upper negation to the latter term. Replace $\dbinom{s}{i-t}$ by $\dbinom{s}{s-\left(i-t\right)} = \dbinom{s}{t-\left(i-s\right)}$. The left hand side then becomes $\left(-1\right)^s \sum\limits_{i=s}^{s+t} \dbinom{-s-1}{i-s} \dbinom{s}{t-\left(i-s\right)}$. Substitute $k$ for $i-s$ in the sum; then ... Jul 27 '19 at 18:19
• ... the sum simplifies to $\dbinom{-1}{t}$ by Chu-Vandermonde convolution. But $\dbinom{-1}{t} = \left(-1\right)^t$. Jul 27 '19 at 18:19

The hint of @darijgrinberg is valuable and deserves an answer by its own.

We obtain \begin{align*} \color{blue}{\sum_{q=s}^{s+t}}&\color{blue}{(-1)^q\binom{q}{s}\binom{s}{q-t}}\\ &=\sum_{q=0}^t(-1)^{q+s}\binom{q+s}{q}\binom{s}{q+s-t}\tag{1}\\ &=(-1)^s\sum_{q=0}^t\binom{-s-1}{q}\binom{s}{t-q}\tag{2}\\ &=(-1)^s\binom{-1}{t}\tag{3}\\ &=(-1)^s\frac{(-1)(-2)\cdots(-t)}{t!}\\ &\,\,\color{blue}{=(-1)^{s+t}} \end{align*} and the claim follows.

Comment:

• In (1) we shift the index to start with $$q=0$$.

• In (2) we use the binomial identities $$\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$$ and $$\binom{p}{q}=\binom{p}{p-q}$$.

• In (3) we apply the Chu-Vandermonde identity.

We seek to verify that

$$\sum_{q=s}^{s+t} (-1)^q {q\choose s} {s\choose q-t} = (-1)^{s+t}$$

where $$s\ge t\ge 0.$$ The LHS is

$$\sum_{q=0}^{t} (-1)^{s+q} {s+q\choose s} {s\choose s+q-t} \\ = \sum_{q=0}^{t} (-1)^{s+q} {s+q\choose s} {s\choose t-q} \\ = (-1)^s [z^t] (1+z)^s \sum_{q=0}^{t} (-1)^{q} {s+q\choose s} z^q.$$

The coefficient extractor controls the range of the sum and we may write

$$(-1)^s [z^t] (1+z)^s \sum_{q\ge 0} (-1)^{q} {s+q\choose s} z^q \\ = (-1)^s [z^t] (1+z)^s \frac{1}{(1+z)^{s+1}} \\ = (-1)^s [z^t] \frac{1}{1+z} = (-1)^s (-1)^t = (-1)^{s+t}.$$

This is the claim.

• Answer verified. (+1) Jul 28 '19 at 20:03