0
$\begingroup$

I came across this identity in my research, but have not been able to prove it. When I entered the LHS of the identity in mathematica, to my surprise, it popped out the RHS, which I presume means the identity is known and coded into mathematica. However, I am struggling to find documentation for it. I tried Gould (and it may very well be in there), but I didn't find it. I would like to cite a source for it, and "mathematica" is not a great one. Any ideas? Here is the identity:

$$\sum\limits^{r}_{k=0} \binom{k + i}{i}\binom{r - k + j}{j} = \binom{i + j + 1 + r}{r}$$

$\endgroup$
2
  • $\begingroup$ I know you asked for a reference, not a proof. But: using the known generating function $f_i(x) = \sum_{k=0}^\infty \binom{k+i}i x^k = 1/(1-x)^{i+1}$, it's easy to see that the left-hand side is the coefficient of $x^r$ in $f_i(x)f_j(x) = f_{i+j+1}(x)$. $\endgroup$
    – Greg Martin
    Jul 27, 2016 at 6:19
  • 1
    $\begingroup$ Consider the product $(1-x)^{-i}(1-x)^{-j}$. $\endgroup$
    – Pedro ♦
    Jul 27, 2016 at 6:21

1 Answer 1

Reset to default
1
$\begingroup$

$$\begin{align*} \sum_{k=0}^r\binom{k+i}i\binom{r-k+j}j&=\sum_{k=0}^r\binom{k+i}k\binom{r-k+j}{r-k}\\ &\overset{(1)}=\sum_{k=0}^r(-1)^k\binom{-i-1}k(-1)^{r-k}\binom{-j-1}{r-k}\\ &=(-1)^r\sum_{k=0}^r\binom{-i-1}k\binom{-j-1}{r-k}\\ &\overset{(2)}=(-1)^r\binom{-i-j-2}r\\ &\overset{(1)}=(-1)^r(-1)^r\binom{r+i+j+1}r\\ &=\binom{r+i+j+1}r \end{align*}$$

The steps labelled $(1)$ involve negating the upper indices of binomial coefficients, and the step labelled $(2)$ uses Vandermonde’s identity.

$\endgroup$
2
  • $\begingroup$ Is this elementary enough that it would not require a citation in a paper? This is why I asked for documentation initially. $\endgroup$
    – Max Hopkins
    Jul 27, 2016 at 6:34
  • $\begingroup$ @Max: That might depend on the audience. It's pretty elementary for people who are accustomed to working with identities involving binomial coefficients, since the most natural thing to try works, but it might be quite a stretch for others. You could perhaps submit the paper using it without proof and add an abbreviated version of my calculation if the referee questions it. $\endgroup$
    – Brian M. Scott
    Jul 27, 2016 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.