# Checking an identity involving binomial coefficients

I need some help to check the following identity:

for every $0\leq i\leq l\leq r$ $$\sum_{j=0}^i\binom{r-l+i-j}{i-j}\binom{l-i+j}{j}=\binom{r+1}{i}.$$

Is this true ?

Answering to John, this identity come from a geometric problem. I was computing the top Chern class of a vector bundle of the form $S\otimes Q$, $S$ is a line bundle, and $Q$ a rank $r$ vector bundle whose Chern classes have a particularly easy form. I have a guess for what should be the answer and imposing equality between the two led me to this identity. I am pretty sure my guess is true and this identity indeed holds; it's interesting that it does not depend on $l$. I think it should be possible to prove this with somee induction argument.

• How did you arrive at this answer? – John Jun 3 '16 at 19:12
• Answering to John, this identity come from a geometric problem. I was computing the top Chern class of a vector bundle of the form $S \otimes Q$, $S$ is a line bundle, and $Q$ a rank $r$ vector bundle whose Chern classes have a particularly easy form. I have a guess for what should be the answer and imposing equality between the two led me to this identity. I am pretty sure my guess is true and this identity indeed holds; it's interesting that it does not depend on $l$. I think it should be possible to prove this with some induction argument. – S. S. Jun 3 '16 at 19:56
• I wrote the question as an unregistered user – S. S. Jun 3 '16 at 19:57
• Upper negation (see proofwiki.org/wiki/Negated_Upper_Index_of_Binomial_Coefficient ) yields $\dbinom{l-i+j}{j} = \left(-1\right)^j \dbinom{j-\left(l-i+j\right)-1}{j} = \left(-1\right)^j \dbinom{i-l-1}{j}$ and $\dbinom{r-l+i-j}{i-j} = \left(-1\right)^{i-j} \dbinom{\left(i-j\right)-\left(r-l+i-j\right)-1}{i-j} = \left(-1\right)^{i-j} \dbinom{l-r-1}{i-j}$ and $\dbinom{r+1}{i} = \left(-1\right)^i \dbinom{i-\left(r+1\right)-1}{i} = \left(-1\right)^i \dbinom{i-r-2}{i}$. Now your identity follows from the Chu-Vandermonde identity, applied to $i-l-1$ and $l-r-1$ and $i$. – darij grinberg Jun 3 '16 at 20:07

Yes, that is true, it is the "double convolution" formula.
To put the formula in more general terms, define the binomial in the extended way: $$\left( \matrix{ x \cr m \cr} \right) = \left\{ \matrix{ {{x^{\,\underline {\,m\,} } } \over {m!}}\quad \left| {\;0 \le {\rm integer}\;m} \right. \hfill \cr 0\quad \quad \left| {\;{\rm otherwise}} \right. \hfill \cr} \right.$$ Then the Upper Negation rule tells that $$\left( \matrix{ x \cr m \cr} \right) = \left( { - 1} \right)^m \left( \matrix{ m - x - 1 \cr m \cr} \right)$$ and therefore, applying it twice \eqalign{ & \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,\,i} \right)} {\left( \matrix{ r - l + i - j \cr i - j \cr} \right)\left( \matrix{ l - i + j \cr j \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,\,i} \right)} {\left( { - 1} \right)^i \left( \matrix{ - r + l - 1 \cr i - j \cr} \right)\left( \matrix{ - l + i - 1 \cr j \cr} \right)} = \cr} and by the "simple" convolution $$= \left( { - 1} \right)^i \left( \matrix{ - r + i - 2 \cr i \cr} \right) = \left( \matrix{ r + 1 \cr i \cr} \right)\quad \left| {\;\left\{ \matrix{ {\rm integer}\;i \hfill \cr {\rm real}\;r,l \hfill \cr} \right.} \right.$$


The Question: $\ds{\sum_{j=0}^{k}{r - \ell + k - j \choose k - j}{\ell - k + j \choose j} = {r + 1 \choose k}}$

\begin{align} &\color{#f00}{\sum_{j=0}^{k}{r - \ell + k - j \choose k - j} {\ell - k + j \choose j}} \\[3mm] = &\ \sum_{j=0}^{\infty}{-r + \ell - k + j + k - j - 1\choose k - j}\pars{-1}^{k - j} {-\ell + k - j + j - 1 \choose j}\pars{-1}^{j} \\[3mm] = &\ \pars{-1}^{k}\sum_{j=0}^{\infty}{\ell - r - 1\choose k - j} {k - \ell - 1 \choose j} = \pars{-1}^{k}\sum_{j=0}^{\infty}{\ell - r - 1\choose k - j} {k - \ell - 1 \choose k - \ell -1 - j} \\[3mm] = &\ \pars{-1}^{k}\sum_{j=0}^{\infty}\bracks{\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{\ell - r - 1} \over z^{k - j + 1}}\,{\dd z \over 2\pi\ic}} \bracks{\oint_{\verts{w} = 1^{-}} {\pars{1 + w}^{k - \ell - 1} \over w^{k - \ell - j}} \,{\dd w \over 2\pi\ic}} \\[3mm] = &\ \pars{-1}^{k}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{\ell - r - 1} \over z^{k + 1}} \oint_{\verts{w} = 1^{-}} {\pars{1 + w}^{k - \ell - 1} \over w^{k - \ell}}\sum_{j = 0}^{\infty}\pars{zw}^{j} \,{\dd w \over 2\pi\ic}\,{\dd z \over 2\pi\ic} \\[3mm] = &\ \pars{-1}^{k}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{\ell - r - 1} \over z^{k + 1}} \oint_{\verts{w} = 1^{-}} {\pars{1 + w}^{k - \ell - 1} \over w^{k - \ell}\pars{1 - zw}} \,{\dd w \over 2\pi\ic}\,{\dd z \over 2\pi\ic} \\[3mm] \stackrel{w\ \to\ 1/w}{=}\ &\ \pars{-1}^{k}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{\ell - r - 1} \over z^{k + 1}}\ \overbrace{\oint_{\verts{w} = 1^{+}} {\pars{1 + w}^{k - \ell - 1} \over w - z}\,{\dd w \over 2\pi\ic}} ^{\ds{\pars{1 + z}^{k - \ell - 1}}}\ \,{\dd z \over 2\pi\ic} \\[3mm] = &\ \pars{-1}^{k}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{k - r - 2} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} = \pars{-1}^{k}{k - r - 2 \choose k} \\[3mm] = &\ \pars{-1}^{k}{-k + r + 2 + k - 1 \choose k}\pars{-1}^{k} = \color{#f00}{{r + 1 \choose k}} \end{align}