Let $X_1,...,X_n\stackrel{iid}{\sim}Geom(p)$,$\quad$ $n\in\mathbb{N}$, $n\geq 1$.
To show: $$ A(n):\Longleftrightarrow X:=\sum_{k=1}^n X_k\sim NB(n,p) $$
My current proof:
I'll show $A(n)$ by induction over $n\in\mathbb{N}$:
Basis step:
$A(1):\Longleftrightarrow X = X_1 \sim Geom(p)=NB(1,p)$.
Assumption:
Let $A(n)$ be true for an $n\in\mathbb{N}$.
Induction step: $$ A(n+1):\Longleftrightarrow X:=\sum_{k=1}^{n+1}X_k = \underbrace{ \left(\sum_{k=1}^{n}X_k\right)}_{=:A\sim NB(n,p)} + \underbrace{X_{n+1}}_{=:B\sim Geom(p)} $$ Now let $Z:=A+B$. Then we want to show that $Z\sim NB(n+1,p)$. We'll show this through a convolution. We know that $X_1,...,X_{n+1}$ are independent, therefore $$ \begin{align*} P[Z=z] &=\sum_{a\in Im(A)} p_A(a)\cdot p_B(z-a) \\\\ &=\sum_{a=n}^{z-1}p_A(a)\cdot p_B(z-a) \\\\ &=\sum_{a=n}^{z-1} \overbrace{\binom{a-1}{n-1}p^n(1-p)^{a-n}}^{p_A(a)}\cdot \overbrace{(1-p)^{z-a-1}p}^{p_B(z-a)} \\\\ &=p^{(n+1)}(1-p)^{z-(n+1)}\sum_{a=n}^{z-1} \binom{a-1}{n-1} \\\\ &=\binom{z-1}{(n+1)-1}p^{(n+1)}(1-p)^{z-(n+1)}\sim NB(n+1,p) \end{align*} $$
q.e.d.
Here's my problem:
Could you verify if the proof is correct? And could you explain me the following step: $$ \sum_{a=n}^{z-1} \binom{a-1}{n-1} = \binom{z-1}{(n+1)-1} $$ I just got this step from Wolfram Alpha - I have no idea how to this can be done.
The last step uses an identity known as the hockey stick identity. Have a look here:
http://www.artofproblemsolving.com/wiki/index.php/Combinatorial_identity