# Recursive Sequence Ratio Convergences

I would like to propose a conjecture (I haven't found any ressources covering my hypothesis):

Let $X$ be a recursive sequence of the form

\begin{equation*} X_n = \sum_{i=n-a}^{n-1} X_i \end{equation*}

with $a > 1$ and fixed values for the first $a$ elements, i.e. $X_i \in \mathbb{R} \; \forall i \leq a$. Note that the upper bound for $a$ does not matter. Then

\begin{equation*} \lim_{n \rightarrow \hat{N}} \left|\frac{X_{n+1}}{X_n}\right| \rightarrow 2 \end{equation*}

for $a$ converging to a suitably large number (simulations show a convergence from $a >10$). $\hat{N}$ is a large number such that $\exists \hat{N} = \hat{N} + 1$. The reason for this is that I don't like to work with $\infty$ as even in the limiting case it does not make sense to me because it suggests that there exists a threshold between finite numbers and infinity.

It can easily be shown that for $a = 3$

\begin{equation*} \lim_{n \rightarrow \hat{N}}\frac{X_{n+1}}{X_n} \rightarrow \phi \end{equation*}

with $\phi$ being the golden ratio for $\textbf{any}$ starting values of $X$. Note that if $X_1 = X_2 = 1$ then $X$ is the Fibonacci sequence, if $X_1 = 1$ and $X_2 = 3$ then the Lucas sequence.

I would go about proving convergence for $a = 4$ and then by induction for $a = k + 1$. The problem is, I don't really know how to create a generalization of Binet's Form which is used to prove convergence in the case that $a = 3$. Any suggestions would be much appreciated. Btw, I'm simply trying to do this out of my curiosity for mathematics.

Here is a little R script to investigate the matter (you can change the $\texttt{runif(n)}$ in the last line to any sequence you want, but try to avoid too many negative numbers as the $\texttt{log}$ will not work then).

generate_seq <- function(startX, N) {

seqX <- numeric(N)
a <- length(startX)
seqX[1:a] <- startX

for(i in (a+1):N) {
seqX[i] <- sum(seqX[(i-1):(i-a)])
}

seqX

}

a_hat <- 50
N_hat <- a_hat + 20
plot(sapply(2:a_hat, function(n) exp(diff(log(generate_seq(runif(n), N_hat))))[N_hat-1]), type = "l")


And results of the simulation:

## 1 Answer

Yes, you're correct. The characteristic polynomial of the recursion $x_n = x_{n-1} + \cdots + x_{n-1}$ is $p_a(t) = t^a - (t^{a-1} + t^{a-2} + \cdots + t + 1)$. The general solution of such a linear homogeneous recurrence relations with constant coefficients is $x_n = \sum_{i=1}^a c_i \lambda_i^n$, where $\lambda_i$ are the roots of the characteristic polynomial (assuming the roots are distinct, which they are in this case). In particular, for generic initial values $x_1,\dots,x_a$, it is known that $\lim_{n\to\infty} x_{n+1}/x_n$ is equal to the root of largest modulus.

As it happens, $p_a(t)$ has one real root $\lambda^{(a)}$ between $2-\frac1a$ and $2$, and $a-1$ roots of modulus less than $\frac32$. To see this, consider $(t-1)p_a(t) = t^{a+1} - 2t^a + 1$. This polynomial has $a$ roots inside the circle centered at $0$ of radius $\frac32$ by Rouché's theorem, since $|2t^a| > |t^{a+1}+1|$ on that circle and $2t^a$ has $a$ roots inside it. One of these roots is the extraneous $t=1$ we introduced; the rest are roots of $p_a(t)$. Furthermore, $p_a(2)=1>0$, while one can check that $p_a(2-\frac1a) = -\frac1a 2^a (1-\frac1a)^a +1$ is negative; therefore there must be a real root $\lambda^{(a)}$ in between.

Consequently, $\lim_{n\to\infty} x_{n+1}/x_n = \lambda^{(a)}$, which tends to $2$ as $a$ tends to infinity. Note that this is true for most, but not all, starting values $x_1,\dots,x_a$: well-chosen starting values would make that limit be at most $\frac32$ in modulus.

• I wonder if the convergence is finite or not, i.e. if $\lim X_{n+1}/X_n = 2 - \epsilon_n$ with $\epsilon_n = 0$ if $n$ is finite. Just assume if we take the sequence $2^n$ for all $X_n$ except $X_0 = 2$. It would fulfill the definition of the sequence and every ratio is exactly 2. Now just subtract a small value $\alpha$ from each term. Under which values of $\alpha$ would that have a finite convergence? Or even simpler, assume $a = 3$ and $X_0 = 1$ and $X_1 = \phi$. Then every $X_{n+1}/X_n = \phi$. Thus the "convergence" is finite. Now let $X_1^* = \phi - \alpha$. – David Seres Oct 7 '14 at 17:59
• For a fixed $a$, if the starting values $x_1,\dots,x_a$ are in geometric progression with common ratio $\lambda^{(a)}$, then it will be true that $x_{n+1}/x_n = \lambda^{(a)}$ for all $n$ (this is if-and-only-if as well). But $\lambda^(a)$ is never exactly equal to $2$; it just approaches $2$ as $a\to\infty$. – Greg Martin Oct 7 '14 at 22:10
• What about the second case? There we have exactly $x_{n+1}/x_n = \lambda^{(a)} = \phi = \lim x_{n+1}/x_n$! – David Seres Oct 7 '14 at 23:01
• This case is just the $a=2$ case of what I said, since $\lambda^{(2)} = \phi$. Or maybe I don't understand what you're asking. – Greg Martin Oct 8 '14 at 18:21