1
$\begingroup$

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?

Ben

  • 1
    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.2012-02-16
  • 0
    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$$2012-02-16
  • 0
    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$.2012-02-16
  • 0
    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!2012-02-16
  • 0
    *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.2012-02-16
  • 0
    OK, we can only assume that $n \rightarrow \infty$2012-02-16

0 Answers 0