Does $f(n+1)/f(n)$ converge as $n\rightarrow\infty$ for $f(n)$ defined by a linear recursion, for all linear recursions?
Does the ratio of consecutive terms converge for all linear recursions?
-
0You're not putting any restrictions on the number of terms? – 2010-12-27
-
0No, but I think I may have figured it out. All linear recursions can be expressed as an explicit formula right? Then we can just take the limit using the explicit formula and that will always yield a convergence? – 2010-12-27
-
1I guess you mean linear recursions with constant coefficients? Otherwise there are trivial counterexamples like $f(n+1)=(-1)^n n f(n)$. – 2010-12-27
-
5I think a precise definition of what you mean by "linear recursion" would be helpful. – 2010-12-27
3 Answers
How about $f(n+1)=f(n-1)$ started with $f(0)=0, f(1)=1?$
The general solution for a (finite) linear recurrence is a function of the form $$f(n) = \sum_{i=1}^m P_i(n) \lambda_i^n,$$ where the $P_i$ are polynomials with possible complex coefficients, and the $\lambda_i$ can be complex as well (even if the sequence itself is real, for example a cyclic sequence of minimal period $>2$); and vice versa. If the eigenvalue with maximal modulus is unique, say $\lambda$, then $f(n+1)/f(n) \rightarrow \lambda$. If all eigenvalues of maximal modulus are obtained from one of them by multiplying with (integral) roots of unity, then there is a periodic subsequence with this property (e.g. in Ross's example take every second term). Otherwise, the sequence will be pretty chaotic: for example $f(n) = \cos(n)$.
-
3People may be surprised that $f(n)=\cos n$ is a solution to a linear constant coefficient recurrence, but $f(n+1)=\cos1\cos n-\sin1\sin n$ and $f(n+2)=\cos2\cos n-\sin2\sin n$ lets you find such a 3-term recurrence. – 2011-08-30
-
0You don't need a 3-term recurrence. $f(n) = \cos n$ satisfies the recurrence $f(n) = c f(n-1) - f(n-2)$, where $c = 2 \cos 1$, if I don't make a mistake. – 2017-06-24
As Ross's counterexample points out the answer, of course, is no in general. However there are broad special cases where the answer is yes, which all more or less go back to the Perron-Frobenius theorem. In particular if the recurrence is combinatorial in the sense that it counts the number of words of length $n$ in a regular language, then subject to some reasonable assumptions about the language the limit you are looking at will exist.