Summing the binomial pmf over $n$ I was trying to work out some bounds for a research problem when I came across the innocuous-looking sum:
$$ \sum_{n=k}^{\infty} {n \choose k} p^k (1-p)^{n-k}, \quad k \in \mathbb{N}, \; p \in (0,1)$$
At first I only needed to show that the sum converges, but later I realized that I need to actually do the sum, which looks familiar/easy but apparently isn't.
Trying various Binomial identities didn't go anywhere, but my repertoire is limited. I also eventually realized that for fixed $p$, the sums should not vary too much across $k$ since when $n$ gets big, the difference in $k$ don't matter much. But I'm not sure how to exploit this.
 A: Let $q=1-p$; then you want
$$p^k\sum_{n\ge k}\binom{n}kq^{n-k}=p^k\sum_{\ell\ge 0}\binom{k+\ell}kq^\ell\;.$$
The generating function of the sequence $\left\langle\binom{k+\ell}k:\ell\in\Bbb N\right\rangle$ is
$$\sum_{\ell\ge 0}\binom{k+\ell}kx^\ell=\frac1{(1-x)^{k+1}}\;,$$
so
$$p^k\sum_{n\ge k}\binom{n}kq^{n-k}=\frac{p^k}{(1-q)^{k+1}}=\frac1p\;.$$
A: You could use the negative binomial distribution.
Imagine tossing a biased coin with probability $p$ of getting "heads". 
The chance that the $k+1$st head occurs on trial $n+1$ is ${n\choose k}p^{k+1}(1-p)^{n-k}$ for $n\geq k$. Therefore 
$$1=\sum_{n=k}^\infty {n\choose k}p^{k+1}(1-p)^{n-k}=p \, \underbrace{\sum_{n=k}^\infty {n\choose k}p^{k}(1-p)^{n-k}}_{\mbox{your sum}}.$$    
A: Since $k$ is fixed, we will be essentially finished if we can find 
$$\sum_{n=k}^\infty (n)(n-1)\cdots (n-k+1)x^n,\tag{1}$$
where $x=1-p$.  
Note that $1+x+x^2+\cdots =\frac{1}{1-x}$, and that the expression (1) is obtained by differentiating $1+x+x^2+\cdots$ term by term $k$ times.
