How to compute the sum of random variables of geometric distribution Let $X_{i}$, $i=1,2,\dots, n$, be independent random variables of geometric distribution, that is, $P(X_{i}=m)=p(1-p)^{m-1}$. How to compute the PDF of their sum $\sum_{i=1}^{n}X_{i}$?
I know intuitively it's a negative binomial distribution $$P\left(\sum_{i=1}^{n}X_{i}=m\right)=\binom{m-1}{n-1}p^{n}(1-p)^{m-n}$$ but how to do this deduction?  
 A: Another way to do this is by using moment-generating functions. In particular, we use the theorem, a probability distribution is unique to a given MGF(moment-generating functions).
Calculation of MGF for negative binomial distribution: 
$$X\sim \text{NegBin}(r,p),\ P(X=x) = p^rq^x\binom {x+r-1}{r-1}.$$
Then, using the definition of MGF:
$$E[e^{tX}]=\sum_{x=0}^{\infty}p^rq^x\binom {x+r-1}{r-1}\cdot e^{tx} = p^r(1-qe^t)^{-r}=M(t)^r,$$
where $M(t)$ denotes the moment generating function of a random variable $Y \sim \text{Geo}(p)$. As
$$E[e^{t(X_1+X_2+\dots+X_n)}]=\prod_{i=1}^nE[e^{tX_i}]$$
since they are independent, and we are done.
A: Let $X_{1},X_{2},\ldots$ be independent rvs having the geometric
distribution with parameter $p$, i.e. $P\left[X_{i}=m\right]=pq^{m-1}$
for $m=1,2.\ldots$ (here $p+q=1$). 
Define $S_{n}:=X_{1}+\cdots+X_{n}$.
With induction on $n$ it can be shown that $S_{n}$ has a negative
binomial distribution with parameters $p$ and $n$, i.e. $P\left\{ S_{n}=m\right\} =\binom{m-1}{n-1}p^{n}q^{m-n}$
for $m=n,n+1,\ldots$. 
It is obvious that this is true for $n=1$
and for $S_{n+1}$ we find for $m=n+1,n+2,\ldots$: 

$P\left[S_{n+1}=m\right]=\sum_{k=n}^{m-1}P\left[S_{n}=k\wedge X_{n+1}=m-k\right]=\sum_{k=n}^{m-1}P\left[S_{n}=k\right]\times P\left[X_{n+1}=m-k\right]$

Working this out leads to $P\left[S_{n+1}=m\right]=p^{n+1}q^{m-n-1}\sum_{k=n}^{m-1}\binom{k-1}{n-1}$
so it remains to be shown that $\sum_{k=n}^{m-1}\binom{k-1}{n-1}=\binom{m-1}{n}$.
This can be done with induction on $m$: 

$\sum_{k=n}^{m}\binom{k-1}{n-1}=\sum_{k=n}^{m-1}\binom{k-1}{n-1}+\binom{m-1}{n-1}=\binom{m-1}{n}+\binom{m-1}{n-1}=\binom{m}{n}$

