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.
Best Answer
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$.