Simplifying or approximating $\sum_{k=1}^{\infty}\left(1 - \left(1 - 2^{-k}\right)^n\right)$? Consider a game in which you flip a coin until you flip tails. Your score is then the number of heads you flipped. So, for example, the sequence $H$, $H$, $H$, $T$ has a score of three, while the sequence $T$ has score zero. You play this game $n$ times. Let $X$ denote your maximum score in the game. I'd like to know what $E[X]$ looks like as a function of $n$.
Here's what I know so far. The probability that your score is greater than or equal to some number $k$ is equal to $$\left(1 - \left(1 - 2^{-k}\right)^n\right),$$ which is the probability that you don't have all scores strictly below $k$. We can then write $E[X]$ as follows:
$$\begin{aligned}
E[X] & = \sum_{k = 0}^{\infty} k \cdot Pr[X = k] \\
     & = \sum_{k = 1}^{\infty} Pr[X \ge k] \\
     & = \sum_{k = 1}^{\infty} \left(1 - \left(1 - 2^{-k}\right)^n\right).
\end{aligned}$$
At this point, I'm completely out of my league in terms of sequence manipulations, and I'm not sure how to simplify this or even interpret what this looks like.
I know that I can write
$$(1 - 2^{-k})^n = ((1 - 2^{-k})^{2^{k}})^{n 2^{-k}} \approx e^{-n 2^{-k}},$$
which lets me rewrite the sum as being (approximately)
$$\sum_{k = 1}^{\infty} (1 - e^{-n 2^{-k}}),$$
but (1) I don't know how much this messes up the estimate and (2) I still have no idea how to simplify or manipulate this sum.
I know that for $n \ll 2^k$ that the term in the sum is close to 0 and that for $n \gg 2^k$ the term in the sum is close to 1, so I'm expecting this sum to come out to something like $\alpha \log_2 n + o(\log_2 n)$ or something like that, but I'm not sure how to rigorously quantify this.
Is there a nice way to simplify this sum or otherwise get a decent approximation of it?
(Context: I'm teaching the HyperLogLog estimator and while the full analysis is way too complex to put into a lecture, I'd still like to give some intuitions as to why it works. The game discussed here is equivalent to looking at leading zeros in a random hash, and the distribution of the maximum score is useful for analyzing the expected value of a simple estimator.)
 A: Using @Mike Spivey's answer to this question
$$E_n = \sum_{k=0}^{\infty} (1 - (1-q^k)^n)$$
$$\int_0^{\infty} (1 - (1 - q^x)^n) dx \leq E_n \leq 1 + \int_0^{\infty} (1 - (1 - q^x)^n) dx$$ for $q=\frac 12$ we have
$$\frac{n (\psi (n)+\gamma )+1}{n \log (2)}\leq E_n \leq 1 +\frac{n (\psi (n)+\gamma )+1}{n \log (2)}$$
So, almost exact
$$\sum_{k = 1}^{\infty} \left(1 - \left(1 - 2^{-k}\right)^n\right)\sim \frac{n H_{n-1}+1}{n \log (2)}-\frac{1}{2}$$
For example, for $n=50$, the xact value is
$5.9909779$ while the approximation gives $5.9909812$.
A: Since there is a transition in the sum around $k=\log_2n$ as the OP points out, let's define $y=\log_2n-\log_2\log n$ and $z=\log_2n+\log_2\log_2n$. We have
\begin{align*}
\sum_{1\le k\le y} (1 - (1 - 2^{-k})^n) &\ge (y-1)(1-(1-2^{-y})^n) \\
&= (y-1)(1-(1-\tfrac{\log_e n}n)^n) \\
&= (y-1)(1-(e^{(\log_e n)/n})^n) = (y-1)(1-\tfrac1n).
\end{align*}
On the other hand, using $(1-t)^n \ge 1-tn$ for $0\le t\le 1$, we also have
\begin{align*}
\sum_{k>z} (1 - (1 - 2^{-k})^n) &\le \sum_{k>z} n2^{-k} < n2^{1-z} = \frac2{\log_2 n}.
\end{align*}
Therefore the entire series is at least $y(1-\tfrac1n)-1 = \log_2n+O(\log_2\log n)$ and at most $z + \frac2{\log_2n} = \log_2n+O(\log_2\log n)$ as well.
A: I give an asymptotic approximation and a reference on its solution here Asymptotic equivalent of $\sum_{k=1} ^N\binom{N}{k}\frac{(-1)^{k+1}}{1-p^k}$
Plug in $p=1/2 $ in the following:
$$ \sum_{k=0}^\infty \big(1-(1-p^k)^n \big) \sim \frac{\log{n} + \gamma}{\log{(1/p)}} + 1/2, \quad 0<p<1 $$
