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.

  • $\begingroup$ Bring $(1-p)^n$ out the front, and let $p/(1-p)=x$. Then you are looking for $\sum_d {d\choose k}x^d$, which is slightly simpler. $\endgroup$ – Empy2 Feb 28 '15 at 19:31

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


  • 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$$


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


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.


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.