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:
- Is there any nice (algebraic) proofs of this fact? Or other proofs}? (This has been answered).
- 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.
- 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?
Best Answer
(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.
(3) That identity is called Vandermonde's identity. I believe the variant with the alternating signs is a special case of the Chu–Vandermonde identity.