# Asymptotics of the solution of the following recurrence relation

$f(k)={k \choose k-1} f(k-1) + { k \choose k-2} f(k-2) + .... {k \choose 3} f(3)$

$f(3) = 1$

$k \ge 3$

Even good upper and lower bounds will help me as I am trying to find how this function grows asymptotically.

-
This is quite similar to the recurrence for Bell Numbers: en.wikipedia.org/wiki/Bell_number#Properties_of_Bell_numbers – Aryabhata Jun 5 '11 at 8:23

Consider the exponential generating function $$F(s)=\displaystyle\sum_{k\ge3}f(k)\frac{s^k}{k!}.$$ Your recursion on the coefficients $(f(k))$ can be translated into a functional equation on $F$. Unless I am mistaken, one gets $$F(s)=\frac{s^3}{6(2-\mathrm{e}^s)},$$ hence the first singularity is at $s=\log2$. From there, the asymptotics on $f(k)$ when $k\to+\infty$ is $$f(k)=k^k(\log 2)^k\mathrm{e}^{-k+o(k)}.$$