1
$\begingroup$

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:

Convergence Values

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – David Seres Oct 7 '14 at 17:59
  • $\begingroup$ 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$. $\endgroup$ – Greg Martin Oct 7 '14 at 22:10
  • $\begingroup$ What about the second case? There we have exactly $x_{n+1}/x_n = \lambda^{(a)} = \phi = \lim x_{n+1}/x_n$! $\endgroup$ – David Seres Oct 7 '14 at 23:01
  • $\begingroup$ 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. $\endgroup$ – Greg Martin Oct 8 '14 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.