# Growth of a sequence satisfying a linear recurrence

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

-
Hard to know, it is a vague statement. Certainly it is false unless we put some conditions on, like linear recurrence with constant coefficients. Even with constant coefficients, we would need to worry about examples like $a_{n+2}=2a_n$, $a_1=1$, $a_2=0$, where we have $1$, $0$, $2$, $0$, $4$, $0$, and so on. Certainly with constant coefficients there is an exponential upper bound. – André Nicolas Sep 22 '11 at 21:34
Assuming constant coefficients, many "garden variety sequences" do satisfy this property; so I can imagine saying such a statement informally. But if we attempt to make a formal claim, we run into the objections raised by @André. Can you give a reference to the paper or quote the relevant lines directly so that we get the full context? – Srivatsan Sep 22 '11 at 21:46
It says exactly what I say . But it is not much related to the results of the paper. I just saw it and was curious. Probably the authors were not careful enough at this point. – Mustafa Gokhan Benli Sep 22 '11 at 22:02
Is there a link to the paper? – The Chaz 2.0 Sep 22 '11 at 22:17
u.math.biu.ac.il/~amirgi/papers/amenability_final.pdf look at the bottom of page 6. – Mustafa Gokhan Benli Sep 22 '11 at 22:34

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).

-

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.

-