How to estimate the growth of a recurrence sequence If we have a linear recurrence sequence where each term depends on all previous terms, say
$a_n = \sum_{k=0}^{n-1} \binom{n}{k} a_k, \quad a_0 = 1$
is there any way to estimate the growth of a_n in terms of a Big-O notation?
I suppose the growth must be super-exponential, because if $a_1, \ldots, a_{n-1}$ grows exponentially, say, $q^i$, then we have $a_n = (q+1)^n - q^n$. Hence The exponent grows from $q$ to $q+1$. But I am not sure if this serves as an argument.
Thanks!
 A: This is sequence A000670 in the On-Line Encyclopedia of Integer Sequences. There are many comments, formulas, links, and references there. 
A: A very powerful way to estimate the growth of a recurrence is to look at the analytic properties of the generating function that it implies.  In this case we should take the exponential generating function $f(x) = \sum_{n \ge 0} \frac{a_n}{n!} x^n$, giving the identity
$$2f(x) = e^x f(x) + 1$$
hence $f(x) = \frac{1}{2 - e^x}$ (one can also deduce this by a purely combinatorial argument).  This function is meromorphic, so the growth rate of $a_n$ is dictated by the position of its poles.  The pole closest to the origin is at $x = \ln 2$, which gives $a_n \sim \frac{n!}{(\ln 2)^n}$.  The other poles contribute similar terms.
The wonderful thing about this technique is that it can work even if you can't solve for the generating function because recurrences that imply certain types of identities for the generating function can still control its analytic properties.  The best reference I know for this kind of stuff is Flajolet and Sedgewick's Analytic Combinatorics, which is available free online.
A: I believe you can create two new recurrence sequences each of whose generating function is known which bound the sequence in question tightly. That gives a really good idea of the growth.
