A truncated alternating sum of product of binomial terms

Question

While solving a question I came across the following alternating sum; $C(j,n): = \sum\limits_{i=j}^{n} (-1)^{i}\binom{n+1}{i+1} \binom{i}{j}$ where $j$ and $n$ are integers with $n \geq j \geq 0$.

By hand I computed that $C(j, j+r) = (-1)^{j}$ for small positive integers $r$. I think that $C(j,n) = (-1)^j$ for any $n \geq j \geq 0$. But I couldn't prove it by induction or by using some other known identities. I would appreciate any suggestion or reference.

Answer 1

Here we have Chu-Vandermonde's Identity in disguise.

We obtain \begin{align*} \color{blue}{\sum_{i=j}^n}&\color{blue}{(-1)^i\binom{n+1}{i+1}\binom{i}{j}}\\ &=\sum_{i=0}^{n-j}(-1)^{i+j}\binom{n+1}{i+j+1}\binom{i+j}{i}\tag{1}\\ &=(-1)^j\sum_{i=0}^{n-j}\binom{n+1}{n-j-i}\binom{-j-1}{i}\tag{2}\\ &=(-1)^j\binom{n-j}{n-j}\tag{3}\\ &\,\,\color{blue}{=(-1)^j} \end{align*}

and the claim follows.

Comment:

• In (1) we shift the index to start with $i=0$ and we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

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

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

Answer 2

\begin{align} \sum_{i=j}^{n}(-1)^i\binom{n+1}{i+1}\binom{i}{j}&=(-1)^j\sum_{i=0}^{n}(-1)^i\binom{n+1}{i+1}[x^j](1-x)^i\\&=(-1)^j[x^j]\sum_{i=0}^{n}\binom{n+1}{i+1}(x-1)^i\\&=(-1)^j[x^j]\frac{x^{n+1}-1}{x-1}=(-1)^j. \end{align}