Let $X\sim NB(r,p)$ and $Y\sim NB(s,p)$ be negativ binomials (I use the variant where we count all trials until we reach r successes). Further, they are independent and I am interested in the distribution of $X+Y$. Surely enough, the result is a Negative Binomial again with parameter r+s.
The task however was to prove that using only the convolution formula. Doing that I derived the following
$$P(X+Y=n)=p^{r+s}(1-p)^{n-r-s}\sum_{j=0}^{n-r-s}\binom{n-j-s-1}{r-1}\binom{j+s-1}{s-1}$$
Since I know the result, I know that this holds:
$$\sum_{j=0}^{n-r-s}\binom{n-j-s-1}{r-1}\binom{j+s-1}{s-1}=\binom{n-1}{r+s-1}$$
Does anyone recognize this identity? I would love it if there was a combinatorial proof for it.
EDIT: Thanks to a comment I adapted the combinatorial argument as follows:
We use m objects and choose one object out of m that splits the list of all objects in two halfs. Then we choose x from the left half and y from the right half.
Another way of counting is to choose element j in the list, choosing x from j-1 elements on the left and y from m-j-1 objects from the right half. Obviously j can run only from x+1 to m-y-1. Therefore
$$\binom{m}{x+y+1}=\sum_{j=x+1}^{m-y-1}\binom{j-1}{x}\binom{m-j+1}{y}
=\sum_{k=0}^{m-x-y}\binom{k+x}{x}\binom{m-k-x}{y}$$
Choosing m=n-2, x=s-1, y=r-1 gives the desired result.
Best Answer
Naturally this bears some similarity to Vandermonde's identity, and can be proven using a slightly generalised version that permits negative integers in the top of the binomial coefficient (Chu-Vandermonde on that Wikipedia page). This is perhaps unsurprising given that we're dealing with negative binomials.
Instead, here is a combinatorial proof. Define $a = n-s-1$, $b = s-1$, $x = r-1$, $y = s-1$. Then this is equivalent to the assertion that $$\sum_{j=0}^{a} \binom{a-j}{x} \binom{b+j}{y} = \binom{a+b+1}{x+y+1}.$$ (The upper limit of the sum is actually $a+x$, but all terms where $j > a$ will clearly just resolve to $0$.) We will prove this for all $y \geq b$ (and all constants non-negative).
Now, consider a row of $a+b$ distinct items. The process being described on the LHS is that we split the row into two smaller rows, the rightmost of which has size at least $b$. Then, we select $x$ elements from the left side, and $y$ from the right side. This is clearly equivalent to a process where, given a row of $a+b+1$ items, we select $x+y+1$ of them; the $x+1$-th element from the left of the row is analogous to our "splitting point" from before, and this divides the selection into a left selection of size $x$ and a right selection of size $y$ on a row of size $a+b$ that has been split in two parts. Since $y \geq b$, then this selection trivially also satisfies the constraint that the rightmost row has size at least $b$. Thus a bijection is established and the proof is complete.