Reference and proof of binomial tail identity

Question

May I have a reference and/or proof of this identity? I saw it mentioned on mathoverflow and don't see how to show it.

For $p \in (0,1)$ and $0 \leq k < n$,

$$ \sum_{i=0}^k {n \choose i} p^i (1-p)^{n-i} = (1-p)^{n-k} \sum_{i=0}^k {n-k-1+i \choose i} p^i .$$

I've verified this numerically and tried some applying the binomial theorem to $(1-p)^{k-i}$ on the left, but that didn't seem to help, so I thought I'd ask for a reference.

Update: I have found a combinatorial proof and posted it as an answer below.

Answer 1

After multiplication with $(1-p)^{k-n}$ we want to show for $p \in (0,1)$ and $0 \leq k < n$ \begin{align*} \color{blue}{\sum_{i=0}^k\binom{n}{i}p^i(1-p)^{k-i}=\sum_{i=0}^k\binom{n-k-1+i}{i}p^i}\tag{1} \end{align*}

Both sides of (1) are polynomials in $p$ of degree $k$. We show equality by comparing coefficients of equal powers of $p$. We use the coefficient of operator $[p^t]$ to denote the coefficient of $p^t$ of a series.

We start with the right-hand side of (1) and obtain for $0\leq t \leq k<n$: \begin{align*} [p^t]\sum_{i=0}^k\binom{n-k-1+i}{i}p^i=\color{blue}{\binom{n-k-1+t}{t}}\tag{2} \end{align*}

This was the easy part. Now the left-hand side of (1):

\begin{align*} [p^t]&\sum_{i=0}^k\binom{n}{i}p^i(1-p)^{k-i}\\ &=\sum_{i=0}^t\binom{n}{i}[p^{t-i}](1-p)^{k-i}\tag{2}\\ &=\sum_{i=0}^t\binom{n}{i}\binom{k-i}{t-i}(-1)^{t-i}\tag{3}\\ &=\sum_{i=0}^t\binom{n}{i}\binom{-k+t-1}{t-i}\tag{4}\\ &\,\,\color{blue}{=\binom{n-k+t-1}{t}}\tag{5} \end{align*} in accordance with (2) and the claim follows.

Comment:

• In (2) we apply the rule $[p^{k-j}]A(p)=[p^k]p^jA(p)$. We also set the upper limit of the sum to $t$ since other indices do not contribute to the sum.

• In (3) we select the coefficient of $p^{t-i}$.

• In (4) we use the binomial identity $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k$.

• In (5) we apply the Chu-Vandermonde identity.

Answer 2

I found a combinatorial argument as well.

We want to show $\Pr[\text{Binom}(n,p) \leq k] = (1-p)^{n-k} \sum_{i=0}^k {n-k-1+i \choose i} p^i$.

Imagine a process where we flip coins with bias $p$ until we have seen $n-k$ tails, then stop. The chance that we stop at or before step $n$ is equal to $\Pr[\text{Binom}(n,p) \leq k]$, i.e. the chance that $n$ flips contain at least $n-k$ tails.

Now we calculate the probability a different way.

The number of ways that we can stop at step $t$, for $t \geq n-k$, is the number of ways to have $n-k-1$ tails in the first $t-1$ flips. Of course the $t$th flip must be a tails, since we stop. So the number of ways is ${t-1 \choose n-k-1} = {t-1 \choose t-n+k}$. The probability of each of these ways is $(1-p)^{n-k} p^{t-n+k}$. So the total probability of stopping at or before step $n$ is \begin{align} &\sum_{t=n-k}^n {t-1 \choose t-n+k} (1-p)^{n-k} p^{t-n+k} \\ =& \sum_{i=0}^k {n-k-1+i \choose i} (1-p)^{n-k} p^i \end{align} after reparameterizing by defining $i=t-n+k$, i.e. replacing each $t$ with $i+n-k$.