Prove that $X_1 + ... + X_r \sim NB(r,p)$ Let $X_1,...,X_r$ be independent random variables with geometric distribution $X_i \sim Geometric(p)$. Then $$X_1 + ... + X_r \sim NB(r,p)$$
This is what I have tried:
$$\begin{eqnarray} P(X_1+...+X_r = k) &=& P(X_1 = k - X_2 -...-X_r)
\\&=& P(X_1 = k - j_2 -...-j_r, X_2 = j_2 , .., X_r=j_r)
\\&=& P(X_1 = k - j_2 -...-j_r) \cdot P(X_2 = j_2) \cdot ... \cdot P(X_r = j_r)
\\&=& (1-p)^k \cdot p^r
\end{eqnarray}$$
which is not quite right since we're missing the factor $ {k+r-1 \choose k}$. But where did I go wrong?
 A: $Y = X_1+...+X_r$ is the number of trials until $r$ successes. Note that the last trial must be successful. Therefore $\{Y=k\}$ consists of the following two independent events:


*

*$r-1$ successes in $k-1$ trials;

*Success in the last ($k$-th) trial.


Taking into account that the probability of the first event equals to the probability that a binomial variable with parameters $k-1$ and $p$ equals to $r-1$ we get:
$$
P\{Y=k\} = \left( \begin{array}{c}
k-1 \\
r-1 \\
\end{array} \right)p^{r-1}(1-p)^{k-1-(r-1)}p = \left( \begin{array}{c}
k-1 \\
r-1 \\
\end{array} \right)p^{r}(1-p)^{k-r} 
$$
The last result is the probability mass function corresponding to the following definition of the negative binomial distribution: "the number of trials until $r$ successes" (other definitions of this distribution exist). 
A: When $r=2$ you have 
$$\begin{align}
\mathsf P(X_1+X_2=k) & =\sum_{j_2=0}^k \mathsf P(X_1=k-j_2)\mathsf P(X_2=j_2)
\\ & = \sum_{j_2=0}^k (1-p)^{k-j_2}p\cdot (1-p)^{j_2}p
\\ & = (k+1) (1-p)^kp^2
\end{align}$$
Now extend this to summation over $j_2, .., j_r$ for any $r\leq k$.
$$\begin{align}
\mathsf P(\sum_{i=1}^r X_i=k) & = \sum_{j_2=0}^k\sum_{j_3=0}^{k-j_2}\cdots\sum_{j_r=0}^{k-\sum_{i=2}^r j_i} \left(\mathsf P\left(X_1=k-\sum_{i=2}^r j_i\right)\prod_{i=2}^r\mathsf P(X_i=j_i)\right)
\\ & = (1-p)^k p^r \left(\sum_{j_2=0}^k\sum_{j_3=0}^{k-j_2}\cdots\sum_{j_r=0}^{k-\sum_{i=2}^r j_i} 1\right)
\end{align}$$
Now use a combinatorial argument on that summation.   Hint: What is it counting?
