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.
Best Answer
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.