TITLE: A proof involving an infinite sum
QUESTION [3 upvotes]: 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?

REPLY [4 votes]: 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}
{"set_name": "stack_exchange", "score": 3, "question_id": 1283940}