1
$\begingroup$

I am trying to upper bound $\sum_{l=1}^\infty (1 - n! 2^{-ln} {2^l \choose n})$.

I tried to use the simple ${2^l \choose n} \ge (\frac{2^l}{n})^n$, but then $l$ disappears and it diverges. Any ideas?

1 Answers 1

3

We have

$$ \frac{n!}{2^{kn}} { 2^k \choose n } = \left( 1 - \frac{1}{2^k} \right) \left( 1 - \frac{2}{2^k} \right) \cdots \left( 1 - \frac{n-1}{2^k} \right) \ge 1 - \frac{n(n-1)}{2^{k+1}}.$$

And so

$$\frac{n(n-1)}{2^{k+1}} \ge 1 - \frac{n!}{2^{kn}} { 2^k \choose n }.$$

  • 0
    Very nice. Thank you!2010-11-23