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!

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

3 Answers 3

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.

$\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$ 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.

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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