Reference and proof of binomial tail identity 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.
 A: 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.
A: 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$.
