proof that the binomial sum is equal to 1

Question

I'm trying to prove the following identity:

let $k$ and $s$ be positive integers and let $k\ge s\ge 1$ $$\sum_{i=0}^{k-s} (-1)^i{s-1+i \choose s-1}{k \choose s+i} = 1$$

I've tried to use a generating function method to prove this formula, but I don't see how to apply it here just yet. With all the other methods I got stuck. How can it be proven? Thanks in advance.

Answer 1

I found it convenient to let $d=k-s$, so that

$$\begin{align*} \sum_{i=0}^{k-s} (-1)^i{s-1+i \choose s-1}{k \choose s+i}&=\sum_{i=0}^{k-s}(-1)^i\binom{s-1-i}i\binom{k}{k-s-i}\\ &=\sum_{i=0}^{d}(-1)^i\binom{s-1+i}i\binom{s+d}{d-i}\;. \end{align*}$$

Let

$$f(x)=\sum_{n\ge 0}(-1)^n\binom{s-1+n}nx^n=\sum_{n\ge 0}\binom{s-1+n}n(-x)^n=\frac1{(1+x)^s}$$

and

$$g(x)=\sum_{n\ge 0}\binom{s+d}nx^n=(1+x)^{s+d}\;.$$

Then

$$\sum_{i=0}^{d}(-1)^i\binom{s-1+i}i\binom{s+d}{d-i}$$

is the coefficient of $x^d$ in

$$f(x)g(x)=(1+x)^d\;,$$

which is clearly $1$.

Answer 2

Here is another variation based upon the usage of the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a generating series.

We obtain \begin{align*} \sum_{i=0}^{k-s}&(-1)^i\binom{s-1+i}{s-1}\binom{k}{s+i}\\ &=\sum_{i=0}^{k-s}\binom{-s}{i}\binom{k}{s+i}\tag{1}\\ &=\sum_{i=0}^{\infty}[z^i](1+z)^{-s}[u^{s+i}](1+u)^k\tag{2}\\ &=[u^s](1+u)^k\sum_{i=0}^{\infty}u^{-i}[z^i](1+z)^{-s}\tag{3}\\ &=[u^s](1+u)^k\left(1+\frac{1}{u}\right)^{-s}\tag{4}\\ &=[u^s](1+u)^ku^{s}\left(u+1\right)^{-s}\\ &=[u^{0}](1+u)^{k-s}\\ &=1 \end{align*}

Comment:

• In (1) we use the binomial identity \begin{align*} \binom{-n}{k}=\binom{n+k-1}{k}(-1)^k=\binom{n+k-1}{n-1}(-1)^k \end{align*}

• In (2) we apply the coefficient of operator and set the upper limit of the sum to $\infty$ without changing anything, since we add only zeros.

• In (3) we do some rearrangements and use \begin{align*} [z^{n+k}]A(z)=[z^n]z^{-k}A(z) \end{align*}

• In (4) we use the relationship \begin{align*} A(z)=\sum_{j=0}^\infty a_jz^j=\sum_{j=0}^{\infty}\left([u^j]A(u)\right)z^j \end{align*}