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?
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?
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 }.$$