4 Followed a suggestion from the comments.

I think you can get the precise value (well, within an additive error of one) by a sort of limiting argument. Rather than a sequence of coins, for each $i=1,\ldots,n$ let $P_i$ be a Poisson process with rate $\ln(2)$ so that the probability there is at least one point in an interval of length $1$ is $1-e^{-\ln(2)} = 1/2$. Now let $T$ be the first time $t$ that in each of the Poisson processes, at least one point has fallen. then $\lceil T \rceil$ has the same distribution as the time you are looking for.

Furthermore, $\lceil T \rceil$ T$is distributed as the maximum of$n$exponential random variables with mean$1/\ln(2)$, or in other words as$1/\ln(2)$times the maximum of$n$standard exponentials. The maximum of$n$standard exponentialshas mean$H_n = \sum_{i=1}^n i^{-1}$. (To see thisNext, note that you can find the such a maximum by first considering the minimum, which is exponentially distributed with mean$1/n$, then considering the maximum remaining time for the remaining$n-1$exponentials and using the memoryless property.) property. It follows that$T$is distributed as a sum$E_1+\ldots+E_n$, where the$E_i$are independent and$E_i$has mean$1/i$. It follows that$T$is has mean$H_n/\ln 2$, and so$f(n) = \mathbb{E}(\lceil T\rceil)$has mean in$[H_n/\ln(2),H_n/\ln(2)+1]$. 3 Deleted the false part of my answer. I think you can get the precise value by a sort of limiting argument. Rather than a sequence of coins, for each$i=1,\ldots,n$let$P_i$be a Poisson process with rate$\ln(2)$so that the probability there is at least one point in an interval of length$1$is$1-e^{-\ln(2)} = 1/2$. Now let$T$be the first time$t$that in each of the Poisson processes, at least one point has fallen. then$\lceil T \rceil$has the same distribution as the time you are looking for. Furthermore,$\lceil T \rceil$is distributed as the maximum of$n$exponential random variables with mean$1/\ln(2)$, or in other words as$1/\ln(2)$times the maximum of$n$standard exponentials. The maximum of$n$standard exponentials is again distributed as an exponential, but with has mean$H_n = \sum_{i=1}^n i^{-1}$rather than mean one. (To see this, note that you can find the maximum by first considering the minimum, which is exponentially distributed with mean$1/n$, then considering the maximum remaining time for the remaining$n-1$exponentials and using the memoryless property.) It follows that$T$is exponentially distributed with has mean$\mu= H_n/\ln 2$, and so $\mathbb{P}(\lceil T \rceil = k) = e^{-(k-1)/\mu} - e^{-k/\mu}.$ Thus $$f(n) f(n) = \mathbb{E}(\lceil T \rceil) = \sum_{k=1}^{\infty} ke^{-(k-1)/\mu}- \sum_{k=1}^{\infty} ke^{-k/\mu} = 1+\frac{1}{1-e^{-1/\mu}} = 1+\frac{1}{1-2^{-1/H_n}}. T\rceil) has mean in I know I didn't use generating functions. But on the other hand, I didn't use generating functions.[H_n/\ln(2),H_n/\ln(2)+1]. 2 Added a little detail in the last equation. I think you can get the precise value by a sort of limiting argument. Rather than a sequence of coins, for each i=1,\ldots,n let P_i be a Poisson process with rate \ln(2) so that the probability there is at least one point in an interval of length 1 is 1-e^{-\ln(2)} = 1/2. Now let T be the first time t that in each of the Poisson processes, at least one point has fallen. then \lceil T \rceil has the same distribution as the time you are looking for. Furthermore, \lceil T \rceil is distributed as the maximum of n exponential random variables with mean 1/\ln(2), or in other words as 1/\ln(2) times the maximum of n standard exponentials. The maximum of n standard exponentials is again distributed as an exponential, but with mean H_n = \sum_{i=1}^n i^{-1} rather than mean one. (To see this, note that you can find the maximum by first considering the minimum, which is exponentially distributed with mean 1/n, then considering the maximum remaining time for the remaining n-1 exponentials and using the memoryless property.) It follows that T is exponentially distributed with mean \mu= H_n/\ln 2, and so $\mathbb{P}(\lceil T \rceil = k) = e^{-(k-1)/\mu} - e^{-k/\mu}.$ Thus$$ f(n) = \mathbb{E}(\lceil T \rceil) = \sum_{k=1}^{\infty} (k-1)e^{-(k-1)/\mu} + \sum_{k=1}^{\infty} e^{-(k-1)\mu} ke^{-(k-1)/\mu}- \sum_{k=1}^{\infty} ke^{-k/\mu} = 1+\frac{1}{1-e^{-1/\mu}} = 1+\frac{1}{1-2^{-1/H_n}}.$\$ I know I didn't use generating functions. But on the other hand, I didn't use generating functions.

1