MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 6 added 964 characters in body

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

show/hide this revision's text 5 added 3 characters in body

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\frac{(-1)^{i+1}}{2^i-1}{n\choose f(n)=\sum_{i=1}^n(-1)^{i+1}\frac{2^i}{2^i-1}{n\choose i}. $$

show/hide this revision's text 4 added 204 characters in body

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 if that this formula helps to recover the asymptotic behaviour of $f(n)$, 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\frac{(-1)^{i+1}}{2^i-1}{n\choose i}. $$

show/hide this revision's text 3 added 8 characters in body
show/hide this revision's text 2 deleted 2 characters in body
show/hide this revision's text 1