2 edited body

If we have a linear recurrence sequence where each term depends on all previous terms, say

$a_n = \sum_{i=0}^{n-1} 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!

1

# 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_{i=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!