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!



How to estimate the growth of a recurrence sequence
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.


