How can one solve the following recurrence relation?


$f(n) = 1 + \frac{1}{2^n} \sum\_{k = 0}^n {{n}\choose{k}} f(k)$


$f(0) = 0$


As it happens, I can show $f(n) = \Theta(\log n)$ through other means (see below). But I'd like to know how to solve the recurrence "directly".


The recurrence relation comes from the following coin flipping problem. There are $n$ independent, unbiased coins, and we toss all of then for a number of rounds. Let $T(n)$ be the first round when each coin has got head at least once (ie, $T(n) = \text{arg} \min\_t \text{s.t.} H\_t(i) \geq 1; \forall i \in [n]$, where $H\_t(i)$ is the number of heads the $i^{th}$ coin has got in the first $t$ rounds). Then one can see that $E(T(n))$ fulfills the recurrence relation mentioned above.


To see that $E(T(n)) = O(\log n)$, note that we reduce the number of coins who haven't gotten head yet by a factor of 2, in expectation. The $\log n$ bound follows routinely from that. On the other direction (ie, $E(T(n)) = \Omega(\log n)$), let $S = \log n/20$. Then at time $S$ with high probability, a large number of coins will still be "headless", from which the lower bound follows.



Coin flipping and a recurrence relation
The exponential generating function of the sequence $(f(n))$ is 
$$
\sum\_{n\ge0}f(n)\frac{s^n}{n!}=\mathrm{e}^{s}\sum\_{k\ge0}(1-\mathrm{e}^{-s/2^k}).
$$
Not sure that this formula helps to recover the asymptotic behaviour of $f(n)$ when $n\to\infty$, though, even if it yields a few equivalent expressions of every $f(n)$, such as
$$
f(n)=\sum\_{k\ge0}(1-(1-2^{-k})^n),
$$
or
$$
f(n)=\sum\_{i=1}^n(-1)^{i+1}\frac{2^i}{2^i-1}{n\choose i}.
$$




---


**Edit** (Most of the following was explained in comments by Emil Jeřábek. It is presented to show how far one can go using the expressions of $f(n)$ written above.)


Fix $n\ge2$ and recall the first expression of $f(n)$, as a sum over $k$ of $$x\_k=1-(1-2^{-k})^n.
$$
Since the sequence $(x\_k)$ is nonincreasing, $f(n)\ge ix\_i$ for every fixed $i$. On the other hand, $x\_k\le1$ and $x\_k\le n2^{-k}$ for every $k$, hence $f(n)\le i+n2^{-i}$. 


Choose $i\ge1$ such that $i\le\log\_2n < i+1$. Then $n/2 < 2^i\le n$ hence $x\_i\ge1-(1-1/n)^n>1-1/\mathrm{e}$. 


Finally, $f(1)=2$ hence, for every $n\ge1$,
$$
(1-1/\mathrm{e})(\log\_2(n)-1) < f(n)\le\log\_2(n)+2.
$$
These estimates can be upgraded to a precise asymptotics as follows. Fix $a<1$ and choose $i$ as close as possible to $a\log\_2n$. Then $(1-n^{-a})^n\to0$ hence $x\_i\to1$ and $f(n)\ge ix\_i\ge a\log\_2(n)(1+o(1))$. 


This proves that $f(n)=\log\_2(n)+o(\log\_2(n))$ when $n\to+\infty$.


