CDF for Negative Binomial Distribution

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.

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*}

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.