A proof involving an infinite sum

Question

I am trying to prove that there exist constants $C_1 > 0$, $C_2>0$ such that$$C_1 \log N \geq\sum_{k=1}^\infty(1 - (1- 1/2^k)^N) \geq C_2\log N$$ where $N\in Z^+$. Could you please give me something to start with?

Answer 1

It doesn't work for $N = 1$, since $\log 1 = 0$, but the sum of the series is $1$ for $N = 1$. Whether that is fixed by excluding $N = 1$ or by altering the upper bound - be that $1 + C_1\log N$ or $C_1 \log (N+1)$ or some other way - is up to you.

For $N \geqslant 2$, we can obtain an upper bound by splitting the sum at $m_N := \left\lfloor\frac{2\log N}{\log 2}\right\rfloor$.

$$\sum_{k=1}^{m_N} \bigl(1 - (1-2^{-k})^N\bigr) \leqslant \sum_{k=1}^{m_N} 1 = m_N < 3\log N$$

is easy to see, and for the remainder of the series we use

$$\log (1-x) \geqslant -2x$$

for $0 \leqslant x \leqslant \frac{1}{2}$ and $e^{x} \geqslant 1+x$. From that we obtain

\begin{align} \bigl(1-2^{-k}\bigr)^N &= \exp \bigl(N\log (1-2^{-k})\bigr)\\ &\geqslant 1 + N\log (1-2^{-k})\\ &\geqslant 1 - \frac{N}{2^{k-1}} \end{align}

and therefore

$$\sum_{k=m_N+1}^\infty \bigl(1-(1-2^{-k})^N\bigr) \leqslant \sum_{k=m_N+1}^\infty \frac{N}{2^{k-1}} = \frac{4N}{2^{m_N+1}}.$$

Now $m_N+1 > \frac{2\log N}{\log 2}$ and therefore $2^{m_N+1} > N^2$, so

$$\sum_{k=m_N+1}^\infty \bigl(1-(1-2^{-k})^N\bigr) < \frac{4}{N},$$

which we can bound by $3\log N$, giving an overall (not at all tight) bound

$$\sum_{k=1}^\infty \bigl(1-(1-2^{-k})^N\bigr) < 6\log N$$

for $N \geqslant 2$.

For the lower bound, we note that $1-(1-2^{-k})^N$ is decreasing (in $k$), so

\begin{align} \sum_{k=1}^\infty \bigl(1-(1-2^{-k})^N\bigr) &\geqslant \sum_{k=1}^{\left\lceil \frac{\log N}{\log 2}\right\rceil} \bigl(1-(1-2^{-k})^N\bigr)\\ &\geqslant \biggl(1 - \biggl(1-2^{-\left\lceil\frac{\log N}{\log 2}\right\rceil}\biggr)^N\biggr)\frac{\log N}{\log 2}\\ &\geqslant \biggl(1 - \biggl(1 - \frac{1}{2N}\biggr)^N\biggr) \frac{\log N}{\log 2}\\ &\geqslant \frac{1-e^{-1/2}}{\log 2}\log N. \end{align}