CDF for Negative Binomial Distribution I am trying to show that the following statement is true.
$$
\sum_{x = r}^{X}\binom{x-1}{r-1}p^r(1-p)^{x-r} =
\sum_{x = r}^{X}\binom{X}{x}p^x(1-p)^{X-x}
$$
Where $X$ and $r$ and $p$ are constants, with $X \geq r$, and $ 0 \leq p \leq 1.$
How did I get there? Well, this is the story:
Consider a sequence of independent binomial trials, each one producing the result success or failure, with probabilities $p$, and $1-p$, respectively.
Let $x$ be the total number of trials which must be carried out in order to attain exactly $r$ successes.
Knowing that the probability mass function for this Negative Binomial Distribution is as follows,
$P(x=X)=\binom{X-1}{r-1}p^r(1-p)^{X-r}$, (for $X \geq r$),
I was trying to prove the following about the corresponding Cumulative Distribution Function.
$P(x \leq X)=\sum_{x=r}^{x=X}\binom{x-1}{r-1}p^r(1-p)^{x-r}=1-\sum_{x=0}^{x=r-1}\binom{X}{x}p^x(1-p)^{X-x}$     
I started out with the following:
$\sum_{x=r}^{\infty}\binom{x-1}{r-1}p^r(1-p)^{x-r}=1$, 
which can be recast as below. (Relation I)
$\sum_{x=r}^{x=X}\binom{x-1}{r-1}p^r(1-p)^{x-r}+\sum_{x=X+1}^{\infty}\binom{x-1}{r-1}p^r(1-p)^{x-r}=1$ 
In addition, from binomial theorem, we have:
$\left ( p+(1-p) \right )^X=\sum_{x=0}^{x=X}\binom{X}{x}p^x(1-p)^{X-x}=1$
Which can be restated in Relation II as below.
$\sum_{x=0}^{x=r-1}\binom{X}{x}p^x(1-p)^{X-x}+\sum_{x=r}^{x=X}\binom{X}{x}p^x(1-p)^{X-x}=1$
Comparing the relations I and II with the expression for the CDF, the proof boils down to verification of the following:
$\sum_{x=r}^{x=X}\binom{x-1}{r-1}p^r(1-p)^{x-r}=\sum_{x=r}^{x=X}\binom{X}{x}p^x(1-p)^{X-x}$
Any idea how to continue form this point onward?
Thanks.
 A: Let's do some substitutions first do make this look a little nicer: If we let $k=x-r, n=r, m=X-n$ and $q=1-p$, the identity can be written as
$$\sum_{k=0}^m \binom{n+k-1}{k}q^k=\sum_{k=0}^m \binom{m+n}{m-k}q^{m-k}(1-q)^{k}$$
and changing $k \to m-k$ on the RHS, we obtain the equivalent
$$\sum_{k=0}^m \binom{n+k-1}{k}q^k=\sum_{k=0}^m \binom{m+n}{k}q^k(1-q)^{m-k}$$
Now, both sides are polynomials in $q$ of degree $m$, so it suffices to compare the coefficients.
The coefficient of $q^s$ of the LHS is just $\binom{n+s-1}{s}$. On the RHS, for specific $k$, the coefficient of $q^s$ in the summand is just
$$(-1)^{s-k}\binom{m+n}{k}\binom{m-k}{m-s}$$
So we are left to prove the identity
$$\sum_{k=0}^s (-1)^{s-k}\binom{m+n}{k} \binom{m-k}{m-s}=\binom{n+s-1}{s}$$
Noting that $(-1)^s\binom{n+s-1}{s}=\binom{-n}{s}$, we see that this identity is a special case of the general identity
$$\sum_{k=0}^{\infty} (-1)^k \binom{N}{k} \binom{a-k}{b}=\binom{a-n}{b-n}$$
where $N=m+n, a=m, b=m-s$. The latter identity can be found e.g. here.
A: Here is another  variation of the theme. It is convenient to  use the  coefficient of  operator  $[z^r]$  to denote the coefficient of $z^r$ of a series. This way we can write e.g.
\begin{align*}
[z^r](1+z)^t=\binom{t}{r}
\end{align*}

We observe LHS and RHS are polynomials in $p$ with lowest degree $r$ and highest degree $X$.
We prove the polynomials 
  \begin{align*}
G(p)&=\sum_{j=r}^X\binom{j-1}{r-1}p^r(1-p)^{j-r}\qquad\qquad\qquad 0\leq r \leq X, 0\leq p\leq 1\\
H(p)&=\sum_{j=r}^X\binom{X}{j}p^j(1-p)^{X-j}
\end{align*}
  are equal by showing equality of the coefficients
  \begin{align*}
[p^t]G(p)=[p^t]H(p)\qquad\qquad\qquad\qquad\qquad\qquad& r\leq t\leq X
\end{align*}

$$ $$

We obtain
  \begin{align*}
[p^t]G(p)&=[p^t]\sum_{j=r}^X\binom{j-1}{r-1}p^r(1-p)^{j-r}\\
&=\sum_{j=r}^X\binom{j-1}{r-1}[p^{t-r}]\sum_{k=0}^{j-r}\binom{j-r}{k}(-p)^k\tag{1}\\
&=\sum_{j=r}^X\binom{j-1}{r-1}\binom{j-r}{t-r}(-1)^{t-r}\tag{2}\\
&=(-1)^{t-r}\binom{t-1}{r-1}\sum_{j=t}^X\binom{j-1}{t-1}\tag{3}\\
\end{align*}

Comment:


*

*In (1) we use the linearity of the coefficient of operator and apply the rule $[z^{t-r}]A(z)=[z^t]z^rA(z)$.

*In (2) we select the coefficient of $p^{t-r}$.

*In (3) we use the binomial identity $$\binom{j-1}{r-1}\binom{j-r}{t-r}=\binom{t-1}{r-1}\binom{j-1}{t-1}$$ and we set the lower limit of the sum to  $j=t$ since otherwise $\binom{j-1}{t-1}=0$.

Since
  \begin{align*}
\sum_{j=t}^X&\binom{j-1}{t-1}=\sum_{j=0}^{X-t}\binom{t+j-1}{j}=\sum_{j=0}^{X-t}\binom{-t}{j}(-1)^j\\
&=\sum_{j=0}^{X-t}[z^j](1+z)^{-t}(-1)^j\\
&=[z^0](1+z)^{-t}\sum_{j=0}^{X-t}\left(-\frac{1}{z}\right)^j\\
&=[z^0](1+z)^{-t}\frac{1-\left(-\frac{1}{z}\right)^{X-t+1}}{1+\frac{1}{z}}\\
&=(-1)^{X-t}[z^{X-t}](1+z)^{-(t+1)}\\
&=(-1)^{X-t}\binom{-(t+1)}{X-t}\\
&=\binom{X}{t}
\end{align*}
we obtain from (3)
  \begin{align*}
[p^t]G(p)=(-1)^{t-r}\binom{X}{t}\binom{t-1}{r-1}\qquad\qquad r\leq t\leq X
\end{align*}

And now the RHS

We obtain using the same techniques as above
  \begin{align*}
[p^t]H(p)&=[p^t]\sum_{j=r}^X\binom{X}{j}p^j(1-p)^{X-j}\\
&=\sum_{j=r}^X\binom{X}{j}[p^{t-j}]\sum_{k=0}^{X-j}\binom{X-j}{k}(-p)^k\\
&=\sum_{j=r}^X\binom{X}{j}\binom{X-j}{t-j}(-1)^{t-j}\\
&=(-1)^t\binom{X}{t}\sum_{j=r}^t\binom{t}{j}(-1)^j\tag{4}
\end{align*}

Comment:


*

*In (4) we use the binomial identity 
\begin{align*}
\binom{X}{j}\binom{X-j}{t-j}=\binom{X}{t}\binom{t}{j}
\end{align*}
and we also set the upper limit of the sum to $j=t$ since otherwise $\binom{t}{j}=0$.



Since
  \begin{align*}
\sum_{j=r}^t&\binom{t}{j}(-1)j=\sum_{j=0}^{t-r}\binom{t}{j+r}(-1)^{j+r}\\
&=\sum_{j=0}^\infty[z^{j+r}](1+z)^t(-1)^{j+r}\tag{5}\\
&=[z^r](1+z)^t(-1)^r\sum_{j=0}^\infty\left(-\frac{1}{z}\right)^j\\
&=(-1)^r[z^r](1+z)^t\frac{1}{1+\frac{1}{z}}\\
&=(-1)^r[z^{r-1}](1+z)^{t-1}\\
&=(-1)^r\binom{t-1}{r-1}
\end{align*}

Comment:


*

*In (5) we set the upper limit to $\infty$ without changing anything since we are adding zeros only.

*In (6) we use the formula of the geometric series expansion.

we obtain from (4)
  \begin{align*}
[p^t]H(p)=(-1)^{t}\binom{X}{t}\binom{t-1}{r-1}\qquad\qquad r\leq t\leq X
\end{align*}

showing the coefficients of $G(p)$ and $H(p)$ are equal. We finally conclude:

The following is valid
  \begin{align*}
G(p)=H(p)=\sum_{j=r}^X(-1)^{j}\binom{X}{j}\binom{j-1}{r-1}p^j
\end{align*}

A: Suppose we seek to prove that
$$\sum_{k=0}^m {n+k-1\choose k} q^k
= \sum_{k=0}^m {m+n\choose m-k} q^{m-k} (1-q)^k.$$
The RHS is
$$\sum_{k=0}^m {m+n\choose k} q^{k} (1-q)^{m-k}.$$
Extracting the coefficient on $q$ on the RHS we get
$$[q^p] \sum_{k=0}^m {m+n\choose k} q^{k} (1-q)^{m-k}
= \sum_{k=0}^m {m+n\choose k} [q^p] q^{k} (1-q)^{m-k}
\\ = \sum_{k=0}^m {m+n\choose k} [q^{p-k}] (1-q)^{m-k}.$$
Now
$$[q^{p-k}] (1-q)^{m-k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{p-k+1}} (1-z)^{m-k} \; dz.$$
Observe that this vanishes when $p\lt  k$ as needed. Now by inspection
of the original RHS we see that we may assume $p\le m.$ Therefore when
$k\gt m$ the integral vanishes and we  may extend the range of the sum
to $m+n$, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{p+1}} (1-z)^{m} 
\sum_{k=0}^{m+n} {m+n\choose k} \frac{z^k}{(1-z)^k}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{p+1}} (1-z)^{m} 
\left(1+\frac{z}{1-z}\right)^{m+n}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{p+1}} (1-z)^{m} 
\frac{1}{(1-z)^{m+n}}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{p+1}}
\frac{1}{(1-z)^{n}}
\; dz
\\ = {p+n-1\choose p}.$$
This is the claim.
A: We may prove it this way too. (Symbols are a bit different, apologies for that).
We want to show that
$$
\sum_{j=r}^n \binom{j-1}{r-1}  (1-p)^{j-r}
 =  \sum_{j=r}^{n} \binom{n}{j} p^{j-r} (1-p)^{n-j}
$$
For $n=r$, LHS = 1 = RHS.
Assume the result is true for $n = r + m$, we prove it is true for $n = r + m + 1$. 
LHS =
$$ \sum_{j=r}^{r+m+1} \binom{j-1}{r-1}  (1-p)^{j-r}
 = \sum_{j=r}^{r+m} \binom{j-1}{r-1}  (1-p)^{j-r} +  \binom{r+m}{r-1} (1-p)^{m+1}\\
  =^{(Assumption)}  \sum_{j=r}^{r+m} \binom{r+m}{j} p^{j-r}  (1-p)^{r+m-j} +  \binom{r+m}{r-1} (1-p)^{m+1} \\
=(*) \sum_{j=r}^{r+m} \binom{r+m+1}{j} p^{j-r}  (1-p)^{r+m-j} - \sum_{j=r}^{r+m} \binom{r+m}{j-1} p^{j-r}  (1-p)^{r+m-j} + \binom{r+m}{r-1} (1-p)^{m+1} + p \sum_{j=r}^{r+m} \binom{r+m+1}{j} p^{j-r}  (1-p)^{r+m-j} - p\sum_{j=r}^{r+m} \binom{r+m+1}{j} p^{j-r}  (1-p)^{r+m-j} \\
= \sum_{j=r}^{r+m} \binom{r+m+1}{j} p^{j-r}  (1-p)^{r+m+1-j} + \sum_{j=r}^{r+m} \binom{r+m+1}{j} p^{1+j-r}  (1-p)^{r+m-j} - \sum_{j=r}^{r+m} \binom{r+m}{j-1} p^{j-r}  (1-p)^{r+m-j} + \binom{r+m}{r-1} (1-p)^{m+1} + p^{m+1} - p^{m+1}\\
= \sum_{j=r}^{r+m+1} \binom{r+m+1}{j} p^{j-r}  (1-p)^{r+m+1-j} + A.
$$
Here
$$A = (*) \sum_{j=r}^{r+m} \Bigg\{ \binom{r+m}{j} + \binom{r+m}{j-1}  \Bigg\} p^{1+j-r}  (1-p)^{r+m-j} - \sum_{j=r}^{r+m} \binom{r+m}{j-1} p^{j-r}  (1-p)^{r+m-j} +  \binom{r+m}{r-1}  (1-p)^{m+1} - p^{m+1}\\
 = \sum_{j=r}^{r+m} \binom{r+m}{j} p^{1+j-r}  (1-p)^{r+m-j} - \sum_{j=r}^{r+m} \binom{r+m}{j-1} p^{j-r}  (1-p)^{r+m+1-j} + \binom{r+m}{r-1}  (1-p)^{m+1} - p^{m+1}\\
= \sum_{j=r}^{r+m} \binom{r+m}{j} p^{1+j-r}  (1-p)^{r+m-j}  - \sum_{j'=r-1}^{r+m-1} \binom{r+m}{j'} p^{j'-r+1}  (1-p)^{r+m-j'} + \binom{r+m}{r-1}  (1-p)^{m+1} - p^{m+1} = 0.
 $$
The equalities with $(*)$ make use of [Pascal rule]https://en.wikipedia.org/wiki/Pascal%27s_rule#:~:text=In%20mathematics%2C%20Pascal's%20rule%20(or,natural%20numbers%20n%20and%20k%2C&text=is%20a%20binomial%20coefficient%3B%20one,(1%20%2B%20x)n.
