Estimation of series

Let $n \geq 2$. Prove that:

$$\sum_{k=1}^{\infty}\left [ 1- \left ( 1-2^{-k} \right )^n \right ] \simeq \ln n $$

Solution



We note that:

$$\frac{1}{m+1}= \int_{0}^{1} x^m \, {\rm d}x= \sum_{k=0}^{\infty}\int_{1-1/2^k}^{1-1/2^{k+1}}x^m \, {\rm d}x\leq \sum_{k=1}^{\infty}\frac{1}{2^k}\left ( 1- \frac{1}{2^k} \right )^m\leq \frac{2}{m+1}$$

Therefore:

$$\begin{aligned}
\sum_{k=1}^{\infty}\left [ 1- \left ( 1- \frac{1}{2^k} \right )^n \right ] &=\sum_{k=1}^{\infty}\sum_{m=0}^{n-1}\frac{1}{2^k}\left ( 1-\frac{1}{2^k} \right )^m \\
 &= \sum_{m=0}^{n-1}\sum_{k=1}^{\infty}\frac{1}{2^k}\left ( 1- \frac{1}{2^k} \right )^m\\
 &\simeq \sum_{m=1}^{n}\frac{1}{m} \\
 &\simeq \ln n 
\end{aligned}$$