# Proof of identity involving product of binomial coefficients

I was playing around and came across the following identity:

For $$0 \leq i \leq l \leq d, \ 1\leq d$$ with $$l$$ and $$d$$ fixed, we have, for each $$i$$, $$\sum_{m=0}^i (-1)^{i-m}\binom{l-m}{l-i}\binom{d}{m} = \binom{d+i-l-1}{i}.$$

Maple experimentally confirms that this identity holds, and I tried (unsuccessfully) to prove it via induction on $$i$$. I have three questions:

1. Is there any nice (algebraic) proofs of this fact? Or other proofs}? (This has been answered).
2. Are all of the assumptions $$0 \leq i \leq l \leq d, \ d\leq 1$$ necessary? I think removing the $$d\leq 1$$ condition is ok provided that you can say that $$\binom{-1}{0}=1$$, but I'm unsure if this definition is reasonable.
3. Are there any references to this identity in the literature? And where can I find the identity $$\sum_k \binom{r}{m+k}\binom{s}{n-k} = \binom{r+s}{m+n}$$ which is used in the linked answer?

Edit: Here is my attempt so far:

Clearly the statement holds for $$i=0$$. So suppose the statement holds for some $$i$$. For $$i+1$$, we have

\begin{align*} & \sum_{m=0}^{i+1} (-1)^{i+1-m}\binom{l-m}{l-i-1}\binom{d}{m} = \sum_{m=0}^{i} (-1)^{i+1-m}\binom{l-m}{l-i-1}\binom{d}{m} + \binom{d}{i+1} \\ &= \sum_{m=0}^{i} (-1)^{i+1-m}\binom{d}{m}\bigg[\binom{l-m+1}{l-i}-\binom{l-m}{l-i}\bigg] + \binom{d}{i+1} \\ &= \sum_{m=0}^{i} (-1)^{i+1-m}\binom{d}{m}\binom{l-m+1}{l-i} - \sum_{m=0}^{i} (-1)^{i+1-m}\binom{d}{m}\binom{l-m}{l-i} + \binom{d}{i+1} \\ &= \sum_{m=0}^{i} (-1)^{i+1-m}\binom{d}{m}\binom{l-m+1}{l-i} + \sum_{m=0}^{i} (-1)^{i-m}\binom{d}{m}\binom{l-m}{l-i} + \binom{d}{i+1} \\ &= \sum_{m=0}^{i} (-1)^{i+1-m}\binom{d}{m}\binom{l-m+1}{l-i} + \binom{d+i-l-1}{i} + \binom{d}{i+1} \end{align*} where the last equality uses the induction hypothesis.

Edit 2: Question 1 has been answered by the linked post. Any responses regarding questions 2 and 3?

• Consider sharing your (failed) attempts.
– hola
May 19, 2021 at 4:00
• @hola I edited my post.
– A.B
May 19, 2021 at 4:18

(2) It's standard to generalize the binomial coefficients to the case where the bottom number is any nonnegative integer (including $$0$$) and the top number is any real or even complex number.