Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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'm trying to upper bound the following sum: $$ \sum\limits_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} e^{-\frac{m}{2^k} } $$ where $n>0$ is fixed and $0\leq m \leq 2^n$.

A trivial upper bound is:

$$ 2^n e^{-\frac{m}{2^n}} $$

One can also expand the e function and obtain:

$$ \sum\limits_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} e^{-\frac{m}{2^k} } =\sum\limits_{i=0}^\infty \frac{(-m)^i}{i!} \sum\limits_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} \left(\frac{1}{2^i}\right)^k = \sum\limits_{i=0}^\infty \frac{(-m)^i}{i!} \left(1+\frac{1}{2^i}\right)^n = ... $$

Have you any idea for a better upper bound?


share|cite|improve this question
By convexity, a lower bound is $2^n\exp\left(-m(3/4)^n\right)$, hence you could explain what kind of refinement of the upper bound you have in mind. – Did Feb 16 '12 at 9:14
Actually, I'am searching for tight, non-trivial upper and lower bounds for $$\sum_{i=0}^{n}\binom{n}{i}(1-\frac{1}{2^i})^m$$ – Benjamin Feb 16 '12 at 9:57
Then you could explain what regime of parameters $(m,n)$ interests you. For example, if $m$ is small, nothing beats the exact formula $\sum\limits_{k=0}^m(-1)^k{m\choose k}(1+2^{-k})^m$. – Did Feb 16 '12 at 10:18
This is my problem: to give an upper bound without the sum. Here $n>0$ and $0 \leq m \leq 2^n$. Thank you for your help! – Benjamin Feb 16 '12 at 10:54
Regime of parameters refers to things like $n\to\infty$ and/or $m\to\infty$ and or $m\ll 2^n$ and/or $m\gg n$, and similar ones. – Did Feb 16 '12 at 13:33

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.