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

  • 0
    OK, we can only assume that $n \rightarrow \infty$2012-02-16

0 Answers 0