Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

3 Answers

up vote 13 down vote accepted

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.

share|improve this answer
4  
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.