3
$\begingroup$

I'm trying to demostrate this for a proof about two random variables(Binomial Negative): $$\sum_{j=0}^k {j+r-1 \choose j}{k-j+s-1 \choose k-j}= {k+r+s-1 \choose k}$$

I know the basics about combinatory so: $$\sum_{j=0}^k {j+r-1 \choose j}\cdot{k-j+s-1 \choose k-j}= \frac{(j+r-1)!}{j!(r-1)!}\cdot\frac{(k-j+s-1)!}{(k-j)!(s-1)!}$$

But i don't know how to arrange them for the proof.

$\endgroup$
2
$\begingroup$

$\dbinom {j+r-1}{j}$ counts the ways to place $j$ indistinct balls into $r$ boxes.

$\dbinom {(k-j)+s-1}{k-j}$ counts the ways to place $k{-}j$ indistinct balls into $s$ boxes.

If we count the ways to take $0$ to $k$ such balls from $k$, place them in $r$ boxes and the rest into $s$ boxes, then we have counted the ways to place $k$ indistinct balls into $r+s$ boxes.

This is counted by $\dbinom{k+(r+s)-1}{k}$.

$\blacksquare$

$$\sum_{j=0}^k\dbinom{j+r-1}{j}\dbinom{(k-j)+s-1}{k-j} ~=~ \dbinom{k+(r+s)-1}{k}$$

$\endgroup$
  • $\begingroup$ As I noted in my answer, Vandermonde's identity claims the $-1$ in the answer should be $-2$, however you also get $-1$ like the assignment. What causes this? Am I reading the identity incorrectly? $\endgroup$ – orlp May 3 '17 at 1:12
  • $\begingroup$ Yes. @orip Note the $j$ and $k$ in the numerator of the binomials. Vandermonde's identity is $$\sum_{j=0}^k \binom{r-1}{j}\binom{s-1}{k-j}=\binom{r+s-2}{k}$$ $\endgroup$ – Graham Kemp May 3 '17 at 1:20
  • $\begingroup$ I went off Vandermonde's identity off of Wikipedia, but for a second I forgot I am cancelling a bounded variable ($j$) outside of the scope of that bounded variable. In other words I was almost assuredly doing something wrong. My bad. $\endgroup$ – orlp May 3 '17 at 1:23
  • $\begingroup$ when the convolution involves both the upper and the lower term, at the bottom you get the sum of the lower terms, at top the sum +1 of the upper terms $\endgroup$ – G Cab Aug 3 '17 at 15:13
2
$\begingroup$

From a negative binomial standpoint, note that

$$\binom{j+r-1}{j}=\left[z^j\right](1-z)^{-r}$$

and

$$\binom{k-j+s-1}{k-j}=\left[z^{k-j}\right](1-z)^{-s}$$

therefore

$$\begin{align}\binom{k+r+s-1}{k}&=\left[z^k\right](1-z)^{-(r+s)}\\&=\left[z^{k}\right](1-z)^{-r}(1-z)^{-s}\\&=\sum_{j=0}^{k}\left[z^j\right](1-z)^{-r}\left[z^{k-j}\right](1-z)^{-s}\\&=\sum_{j=0}^{k}\binom{j+r-1}{j}\binom{k-j+s-1}{k-j}\end{align}$$

$\endgroup$

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.