Unusual binomial sum: $\sum_{d=k}^{n} {d \choose k} p^{d}(1-p)^{n-d}$

Question

Does anyone know how to simplify the following sum? It's been giving me and everyone else I've showed it to quite a bit of trouble. I'm quite confident that this should simplify, but I just can't seem to see how. \begin{equation} \sum_{d=k}^{n} {d \choose k} p^{d}(1-p)^{n-d} \end{equation}

Where k is greater than 1. Please note that the sum varies over the upper index of the binomial. The attempts thus far have pretty much all involved expressing the terms as a series and trying to relate that series to the product of the derivatives of order up to and including d. This method is proving intractable as it only works for k=2, otherwise we get the product of the product (k-1 times) of a series involving higher order derivatives, which is hardly a simplification. Any and all insights are welcome.

Answer 1

We can compute the generating function $$ \begin{align} \sum_{n=k}^\infty\sum_{d=k}^n\binom{d}{k}p^d(1-p)^{n-d}x^n &=\sum_{d=k}^\infty\sum_{n=d}^\infty\binom{d}{k}p^d(1-p)^{n-d}x^n\\ &=\sum_{d=k}^\infty\binom{d}{k}\frac{p^dx^d}{1-(1-p)x}\\ &=(px)^k\sum_{d=0}^\infty\binom{-k-1}{d}\frac{(-1)^dp^dx^d}{1-(1-p)x}\\ &=\frac{(px)^k}{(1-px)^{k+1}}\frac1{1-(1-p)x}\tag{1} \end{align} $$ In the special case of $p=\frac12$, we get $$ \begin{align} \frac{\left(\frac12x\right)^k}{\left(1-\frac12x\right)^{k+2}} &=\sum_{j=0}^\infty\binom{-k-2}{j}(-1)^j\left(\tfrac12x\right)^{k+j}\\ &=\sum_{j=0}^\infty\binom{k+j+1}{j}\left(\tfrac12x\right)^{k+j}\\ &=\sum_{n=k}^\infty\binom{n+1}{k+1}\left(\tfrac12x\right)^n\tag{2} \end{align} $$ From $(1)$, we get $$ \bbox[5px,border:2px solid #C0A000]{\sum_{d=k}^n\binom{d}{k}p^d(1-p)^{n-d}=\left[x^{n-k}\right]\left(\frac{p^k}{(1-px)^{k+1}}\frac1{1-(1-p)x}\right)}\tag{3} $$ In the special case of $p=\frac12$, $(2)$ gives $$ \bbox[5px,border:2px solid #C0A000]{\sum_{d=k}^n\binom{d}{k}\left(\frac12\right)^d\left(\frac12\right)^{n-d}=\binom{n+1}{k+1}\left(\frac12\right)^n}\tag{4} $$

Answer 2

Note: Here's is an answer providing a closed formula for the (simple) special case $p=\frac{1}{2}$. Since the used approach is often helpful to also find a general solution, it indicates that there is presumably no closed formula of OPs expression $$\sum_{d=k}^{n}\binom{d}{k}p^d(1-p)^{n-d}\qquad\qquad 0\leq k\leq n$$

We show the following is valid for $p=\frac{1}{2}$ \begin{align*} \sum_{d=k}^{n} \binom{d}{k} \left(\frac{1}{2}\right)^{d}\left(1-\frac{1}{2}\right)^{n-d}=\frac{1}{2^n}\binom{n+1}{k+1} \end{align*}

We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. So, we can write e.g. $$\binom{d}{k}=[z^k](1+z)^d$$

We start with general $p$, use the shorthand $q:=\frac{p}{1-p}$ and we observe: \begin{align*} \sum_{d=k}^{n}\binom{d}{k}p^d(1-p)^{n-d}&=(1-p)^n\sum_{d=k}^n\binom{d}{k}\left(\frac{p}{1-p}\right)^d\\ &=(1-p)^n\sum_{d=k}^{n}[z^k](1+z)^dq^d\\ &=(1-p)^n[z^k]\sum_{d=k}^{n}\left((1+z)q\right)^d\\ &=(1-p)^n[z^k]\left(\sum_{d=0}^{n}\left((1+z)q\right)^d-\sum_{d=0}^{k-1}\left((1+z)q\right)^d\right)\tag{1}\\ &=(1-p)^n[z^k]\left(\frac{1-\left((1+z)q\right)^{n+1}}{1-(1+z)q} -\frac{1-\left((1+z)q\right)^{k}}{1-(1+z)q}\right)\\ &=(1-p)^n[z^k]\frac{\left((1+z)q\right)^{k}-\left((1+z)q\right)^{n+1}}{1-(1+z)q}\tag{2} \end{align*}

Comment:

• In (1) we apply the formula for finite geometric series

• in (2) we could try to go on by expanding the denominator as series $$\frac{1}{1-(1+z)q}=\sum_{l\geq 0}\left((1+z)q\right)^l$$ and extracting via $[z^k]$ the coefficent of $z^k$. Regrettably, when doing so we will finally come back to the expression where we've started. But at least for the special case $p=\frac{1}{2}$ we can proceed.

We obtain continuing from (2) the

Special case: $p=\frac{1}{2},q=\frac{p}{1-p}=1$

\begin{align*} \frac{1}{2^n}\sum_{d=k}^n\binom{d}{k}&=\frac{1}{2^n}[z^k]\frac{(1+z)^{k}-(1+z)^{n+1}}{-z}\\ &=\frac{1}{2^n}[z^{k+1}]\left((1+z)^{n+1}-(1+z)^{k}\right)\\ &=\frac{1}{2^n}\left(\binom{n+1}{k+1}-\binom{k}{k+1}\right)\\ &=\frac{1}{2^n}\binom{n+1}{k+1} \end{align*}

and conclude

$$\sum_{d=k}^n\binom{d}{k}=\binom{n+1}{k+1}\qquad\qquad 0 \leq k \leq n$$

Answer 3

Here is a formula with $k+2$ terms, rather than $n-k$ terms; that might be an improvement. $$F(x;k,n)=\sum_{d=k}^n{d\choose k}x^d\\ =\frac{x^k}{k!}\sum_{d=0}^{n-k}\frac{d^k}{dx^k}\sum_{d=0}^nx^k\\ =\frac{x^k}{k!}\frac{d^k}{dx^k}(x^{n+1}-1)/(x-1)\\ =(if k=0)(x^{n+1}-1)/(x-1)\\ =(if k=1) \frac{x}1\left[nx^n/(x-1)-(x^{n+1}-1)/(x-1)^2\right]\\ =(if k=2) \frac{x^2}2\left[n(n-1)x^{n-1}/(x-1)-2nx^n/(x-1)^2+2(x^{n+1}-1)/(x-1)^3\right]\\ =(if k=3) \frac{x^3}{3!}\left[\frac{n(n-1)(n-2)x^{n-2}}{x-1}-\frac{3n(n-1)x^{n-1}}{(x-1)^2}+\frac{6nx^n}{(x-1)^3} -\frac{6(x^{n+1}-1)}{(x-1)^4}\right]\\ =\frac{x^k}{(1-x)^{k+1}}-x^n\sum_{h=0}^k{n\choose h}\left(\frac{x}{1-x}\right)^{1+k-h} $$ That still needs to be converted back to a function of $p$, according to my comment on the OP.