# 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!

-
Your argument is certainly not rigorous, but you might be able to turn it into a proof: begin by assuming a_n is bounded by a sequence of exponential growth (a_n < c*r^n) and derive a contradiction. But this is an ad-hoc strategy. – Darsh Ranjan Feb 14 '10 at 18:12
Isn't this the recurrence relation for Bell Numbers? – Pradipta Feb 10 '11 at 0:36

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.

-
The generating function is derived p. 109 of Flajolet and Sedgewick; its asymptotics are found on p. 259. I should point out that we actually have $a_n \sim n!/2 \cdot (1/\log 2)^{n+1}$, which differs by a constant factor from your quick estimate. – Michael Lugo Feb 14 '10 at 14:08

This is sequence A000670 in the On-Line Encyclopedia of Integer Sequences. There are many comments, formulas, links, and references there.

-

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.

-