3
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

(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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .