3
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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 ... $\endgroup$ Jul 27 '19 at 18:19
  • 4
    $\begingroup$ ... the sum simplifies to $\dbinom{-1}{t}$ by Chu-Vandermonde convolution. But $\dbinom{-1}{t} = \left(-1\right)^t$. $\endgroup$ Jul 27 '19 at 18:19
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Answer verified. (+1) $\endgroup$
    – epi163sqrt
    Jul 28 '19 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.