Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I got a general question, that is motivated by a recent problem. So let me first describe the problem and then add the general part: I got a rather simple (using only basic elements) equation, which reads $$ \alpha \leq \sum_{i=0}^{n} (1- \frac{i}{n}) \left(1- \left(1-\frac {\binom{n}{i}}{2^n} \right)^m \right) \prod_{j=0}^{i-1} \left(1-\frac {\binom{n}{j}}{2^n} \right)^m, $$ and I need to find the smallest value of m, such that the inequality is satisfied. It would be fine with me to find a 'good' lower bound, but so far I'm unable to get even a 'bad' lower bound. I tried different approaches, for example, using the famous inequality $$ (1+x) \leq \exp(x), $$ to rewrite the equation as $$ \alpha \leq \exp \left(-m\right) \sum _{i=0}^n \left(1-\left(1-\frac{\binom{n}{i}}{2^n}\right)^m\right) \exp \left( m \binom{n}{i} \, _2F_1(i,n+1;i+1;-1)-\frac{i}{n}\right) $$ where I used the hypergeometric function denoted by F, but I'm still stuck with the sum over i. Therefore I wanted to ask, if anybody knows a good resources where I could learn more about approximating sums in general. I'm a computer science student and although our university is focused on mathematics, I'm still not satisfied with my current set of techniques.

My main interest here is to learn something about approximating sums. For me this particular problem is more of a challenge than a real problem since my long term goal is to get better when approximating equations. Any resources you would recommend?

Thank you very much,

share|cite|improve this question
Wikipedia's article on binomial coefficients has sections on approximations and asymptotics: – marty cohen Aug 18 '15 at 16:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.