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?

  • 3
    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.2011-09-22
  • 0
    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?2011-09-22
  • 0
    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.2011-09-22
  • 0
    Is there a link to the paper?2011-09-22
  • 0
    http://u.math.biu.ac.il/~amirgi/papers/amenability_final.pdf look at the bottom of page 6.2011-09-22
  • 0
    I think the authors mean something like this: "polynomial growth" with degree $d$ (a nonnegative integer) would say $\lim \sup_{n \to \infty} |a_n| n^{-d}$ is a nonzero constant; "exponential growth" would say $\lim \sup_{n \to \infty} |a_n| n^{-d} e^{-kn}$ is a nonzero constant for some nonnegative integer $d$ and positive real $k$. There can't be "exponential decay" in their case because their $a_n$ is always a nonnegative integer (it is counting something). I haven't checked whether values of 0 are possible in their application: I don't know what they would call it if $a_n = 0$ eventually.2011-09-22
  • 0
    My guess is that the paper wants an upper bound on the activity growth, rather than a tight upper+lower bound. Specifically, the quantity "number of length-$n$ words $v$ such that the section $a(v)$ is not the identity" is either $O(n^{d})$ for some $d$ (in which case, the degree is defined to be the smallest such $d$; conveniently, it's an integer), or it is not (in which case the degree is defined to be $\infty$). If we care only about the upper bound, and not a tight bound, the current objections (e.g., sequence could be periodic/oscillating and so on) are no longer applicable.2011-09-22
  • 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.