Proof of the following combinatorial identity

Question

Prove

$$\sum_{m\le i\le k-l} \binom{k-i-1}{l-1} \binom{i-1}{m-1} = \binom{k-1}{m+l-1}$$

where $m$, $l$, $i$, $k$ are positive integers and $k\ge m+l$.

---

Is this related to Vandermonde's identity?

Answer 1

Yes, we have Chu-Vandermonde's Identity in disguise.

We obtain \begin{align*} \color{blue}{\sum_{i=m}^{k-l}}&\color{blue}{\binom{k-i-1}{l-1}\binom{i-1}{m-1}}\\ &=\sum_{i=0}^{k-l-m}\binom{k-i-m-1}{l-1}\binom{i+m-1}{i}\tag{1}\\ &=\sum_{i=0}^{k-l-m}\binom{k-i-m-1}{k-l-m-i}\binom{-m}{i}(-1)^i\tag{2}\\ &=\sum_{i=0}^{k-l-m}\binom{-l}{k-l-m-i}(-1)^{k-m-l}\binom{-m}{i}\tag{3}\\ &=\binom{-l-m}{k-l-m}(-1)^{k-m-l}\tag{4}\\ &\,\,\color{blue}{=\binom{k-1}{m+l-1}}\tag{5} \end{align*}

and the claim follows.

Comment:

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

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

• In (3) we use again $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (4) we apply Chu-Vandermonde's Identity.

• In (5) we use once more $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.