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