I've been solving a complex problem, in which at one step, I have to calculate the following $$ \frac {{n \choose 0} + {n\choose 1} + {n\choose 2} + ... + {n\choose k}}{2^n} $$ The values of n and k can be very large $ \le 10^5$. But since the answer will always be less than 1 ($ k < n$), I was wondering if its calculable doing some modulo trick which will leave me an answer with 4-5 decimal precision.

Thanks in advance.

  • 1
    $\begingroup$ This may be useful (there is, among others, a closed form using the hypergeometric series): mathoverflow.net/questions/17202/… $\endgroup$ – Jean-Claude Arbaut Feb 5 '17 at 10:40
  • $\begingroup$ You could use the similarity to the binomial distribution and approximate it with a normal distribution. And then use that the integrated normal distribution is related to the error function. $\endgroup$ – the_architect Feb 5 '17 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.