|
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 sequenceIf 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!
|
||||
