Tuesday, 16 June 2009

ca.analysis and odes - 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!

No comments:

Post a Comment