0
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Jair Taylor Apr 6 '18 at 19:18
  • $\begingroup$ Of course there are various approximations in terms of the CDF $\Phi$ of the normal distribution. $\endgroup$ – Christian Blatter Apr 16 '18 at 13:19
0
$\begingroup$

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

$\endgroup$

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.