# A combinatoric solution (closed expression) for $\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$

I am trying to find a combinatoric solution for $\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$.

i.e. write it as a closed function (and not as a sum).

I know that in generating functions one can for example multiply the relevant function by $\frac{1}{1-x}$. But this is relevant for combinatoric problems like identical k balls in n cells.

Is there something like that for the formula above?

• There is probably no closed form for this. Often in these kind of sums there is only a formula for the entire sum from $k=0$ to $n$, but not for partial sums. You could probably write it in terms of a hypergeometric function, but that's just giving a name to it. – Jair Taylor Apr 6 '18 at 19:18
• Of course there are various approximations in terms of the CDF $\Phi$ of the normal distribution. – Christian Blatter Apr 16 '18 at 13:19

As mentioned in the comment by Jair Taylor there doesn't appear to be a closed form. The hypergeometric representation is $$Q(i,n,p)=\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k} = (1-p)^{n-i}p^i \binom{n}{i}\; _2F_1 \left(1,i-n;i+1;\frac{p}{p-1}\right)$$ and the generating function is very similar $$\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}x^{k} = (1-p)^{n-i}p^i x^i \binom{n}{i} \;_2F_1 \left(1,i-n;i+1;\frac{p x}{p-1}\right)$$ if you want the generating function over all possible values of $i$, Mathematica claims there is a recursion relation for $$F(x)=\sum_{i=0}^n Q(i,n,p)x^i$$ then if we define a function $y_k(x,p,n)$ where $$y_0 = 0 \\ y_1 = \left(\frac{1}{1-p}\right)^n \\ y_2 = y_1 + \left(y_1-1\right)x %(n-k)p x^2 y_k - x(1+k-p-2kp+np-kpx+npx)y_{k+1} + (1 + k -p-kp + x + kx-px-2kpx+npx)y_{k+2}+(1+k)(p-1)y_{k+3}=0$$ and in general $$y_{k+3} = a(k) y_{k+2} + b(k) y_{k+1} + c(k) y_{k}$$ with $$a(k) = -\frac{(1 + k -p-kp + x + kx-px-2kpx+npx)}{(1+k)(p-1)}\\ b(k) = \frac{x(1+k-p-2kp+np-kpx+npx)}{(1+k)(p-1)} \\ c(k) = -\frac{(n-k)p x^2}{(1+k)(p-1)}$$ then $$F(x) = (1-p)^ny_{n+1}$$