3
$\begingroup$

A paper I am reading says that a sequence satisfying a linear recurrence grows either polynomially or exponentially. Is this easy to see?

  • 0
    If $a_n$ is zero for some $n$ then it is zero for all higher $n$. The paper is mainly concerned with linear activity growth.2011-09-24

2 Answers 2

1

The sequences satisfying a homogeneous linear recurrence with constant coefficients are precisely those of the form

$a_n = \sum_i P_i(n) \lambda_i^n$

where the $P_i$ are polynomials. This standard result can be proven in a variety of ways and found in many places; the first reference that comes to mind is Stanley's Enumerative Combinatorics, Ch. 4.

The conclusion follows if there is a unique largest positive real $\lambda_i$, but not in general (e.g. $a_n$ may be periodic of any given period).

1

Here is a simpler way to see why it $should\ $ be true:

Suppose $a_n = \sum_{i=1}^k c_i a_{n-i}$ where each $c_i \ge 0$ and the initial $a_n \ge 0$ with at least one $a_n > 0$. Then the $a_n$ are increasing for $n > k$, so, if $C = \sum_{i=1}^k c_i$, then $a_n \le C a_{n-1}$, so that $a_n \le C^m a_{n-m}$ for $n \ge m+k$. Setting $m = n-k$, $a_n < C^{n-k} a_k$, so $a_n$ grows at most exponentially.

Similarly, if $c_1 > 0$, then $a_n \ge c_1 a_{n-1}$, so $a_n \ge c_1^{n-k} a_k$, so $a_n$ grows at least exponentially.

This is just a simplification of the standard proof using the characteristic polynomial of the recurrence relation, with assumptions to make everything easy. The full thing naturally takes more work, but this should give you an idea of why the exponential growth holds.