5
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Darsh Ranjan
    Commented Feb 14, 2010 at 18:12
  • $\begingroup$ Isn't this the recurrence relation for Bell Numbers? $\endgroup$
    – Pradipta
    Commented Feb 10, 2011 at 0:36

3 Answers 3

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – Michael Lugo
    Commented Feb 14, 2010 at 14:08
3
$\begingroup$

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

Improve this answer
$\endgroup$
-1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .