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:


which can be recast as below. (Relation I)


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.


Comparing the relations I and II with the expression for the CDF, the proof boils down to verification of the following:


Any idea how to continue form this point onward? Thanks.


3 Answers 3


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.

  • 1
    $\begingroup$ @FelixMarin The idea of working with the coefficient on $q$ is key to an effective solution to this problem. I use it as well in my post. This contribution was first, however, hence (+1). $\endgroup$ Sep 19, 2016 at 23:09

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


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


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


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

  • 1
    $\begingroup$ (+1). This one was not as easy as it looks, but I managed to simplify it after trying quite a few different approaches. $\endgroup$ Sep 19, 2016 at 22:39
  • 1
    $\begingroup$ @MarkoRiedel: Nice work (+1). Here I wanted to calculate straight ahead from OPs starting point. It was nice to see that both binomial coefficients from LHS and RHS are part of the solution. $\endgroup$
    – epi163sqrt
    Sep 20, 2016 at 0:05

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}.$$


$$[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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.