# How to find documentation for or a proof of the following known binomial identity

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}$$

• 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)$. Jul 27, 2016 at 6:19
• Consider the product $(1-x)^{-i}(1-x)^{-j}$.
– Pedro
Jul 27, 2016 at 6:21

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