Proof that negative binomial distribution is a distribution function? In my textbook, a clear proof that the Geometric Distribution is a distribution function is given, namely 
$$\sum_{n=1}^{\infty} \Pr(X=n)=p\sum_{n=1}^{\infty} (1-p)^{n-1} = \frac{p}{1-(1-p))}=1.$$
Then the textbook introduces the Negative Binomial Distribution; it gives a fairly clear explanation for why the PMF of a Negative Binomial random variable $N$ with parameter $r$ is 
$$p\binom{n-1}{r-1}p^{r-1}(1-p)^{n-r} = \binom{n-1}{r-1}p^{r}(1-p)^{n-r} $$
But to show
$$\sum_{n=r}^{\infty} \Pr(N=n)=\sum_{n=r}^{\infty}\binom{n-1}{r-1}p^{r}(1-p)^{n-r}=1$$
the textbook gives (in my opinion) a wordy and informal argument that is nowhere near as clear. 
What is a straightforward algebraic way to prove the above statement; that the Negative Binomial is a distribution function? I also looked at a different probability textbook, plus wolfram.com's definition  before asking.  
 A: It's evident that $\Bbb{P}(N=n)\ge 0$ for $n\ge r$. So you have to prove that $\sum_{n\ge r}\Bbb{P}(N=n)=1$:
$$
\begin{align}
\sum_{n\ge r}\Bbb{P}(N=n)&=\sum_{n\ge r} \binom {n-1} {r-1} p^r \left({1-p}\right)^{n-r}\\
&=\sum_{n\ge r} \binom {n-1} {n-r} p^r \left({1-p}\right)^{n-r}\;\;\quad\quad\text{(symmetry})\\
&=p^r\sum_{j\ge 0} \binom {r+j-1} {j} \left({1-p}\right)^{j}\qquad\text{(substituting }j=n-r)\\
&=p^r\sum_{j\ge 0} (-1)^j \binom{-r}{j}\left({1-p}\right)^{j}\qquad\text{(identity}\tbinom{j+r-1}{j}=(-1)^j \tbinom{-r}{j})\\
&=p^r\sum_{j\ge 0} \binom{-r}{j}\left({p-1}\right)^{j}\\
&=p^r\left(1+(p-1)\right)^{-r} \qquad\qquad\qquad\text{(binomial theorem) }\\
&=1
\end{align}
$$
using the identity
$$
\begin{align}
\binom{j+r-1}{j}&=\frac{(j+r-1)(j+r-2) \cdots r}{j!}\\
&=(-1)^j \frac{(-r-(j-1))(-r-(j-2)) \cdots (-r)}{j!} \\&=(-1)^j \frac{(-r)(-r-1) \cdots (-r-(j-1))}{j!} \\&=(-1)^j \binom{-r}{j}
\end{align}
$$
A: You can show this directly with generating functions: $$\left({z\over 1-z}\right)^r=\left( \sum_{\alpha\geq 1} z^\alpha \right)^r
=\sum_{\alpha_1,\dots, \alpha_r \geq 1} z^{\alpha_1+\cdots +\alpha_r}=\sum_{n\geq r} {n-1\choose r-1} z^n.$$ 
The last equation follows from "stars and bars"
 which gives you the number of compositions of $n$ in $r$ pieces. 
Now substitute in $z=1-p$ to get the result. 
A: The fact that the negative binomial probabilities sum to $1$ is a consequence of the following result (set $x:=1-p$ and rearrange):
Claim: If $|x|<1$ then for each $r=1,2,\ldots$ $$\sum_{n=r}^\infty {n-1\choose r-1}x^{n-r}=(1-x)^{-r}.\tag1$$
Proof: Use induction on $r$. For the base case $r=1$, the claim is that
$\sum_{n=1}^\infty x^{n-1}=(1-x)^{-1}$ when $|x|<1$, which follows from the formula for the sum of a geometric series.
Now suppose (1) holds for $r$. The LHS of (1) is a power series in $x$, with radius of convergence $1$ (by the ratio test), so it can be differentiated term by term to obtain
$$
\sum_{n=r}^\infty{n-1\choose r-1}(n-r)x^{n-r-1}=r(1-x)^{-r-1},\tag2
$$
valid whenever $|x|<1$. The sum on the LHS of (2) can be started at $n=r+1$, since $n=r$ contributes nothing. Rewrite (2) using the identity $(n-r){n-1\choose r-1}=r{n-1\choose r}$, then divide through by $r$. This yields
$$\sum_{n=r+1}^\infty{n-1\choose (r+1)-1}x^{n-(r+1)}=(1-x)^{-(r+1)},\tag3$$
which establishes (1) for $r+1$.
