Recursive Sequence Ratio Convergences

Question

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:

Answer 1

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.