Find $\inf$ and $\sup$ of $a_n = \frac{a_{n-1} + a_{n-2}}{a_{n-3}}$

Solution 1:

(Too long to be in the comments)

This problem (and many related ones) showed up as part of my thesis (not yet finished), so perhaps I will share what I have found on this. This is not an answer, as I have yet to determine why even it is bounded, as many have observed to be quite difficult (at least to me) to show. But I have some qualitative observations, as well as variations of this (at the end).

Indeed, as you plot the sequence $a_n$ given by $a_{n+3}=\frac{a_{n+2}+a_{n+1}}{a_n}$ with $a_0=a_1=a_2=1$, we get (10000 terms of $a_n$.)

To me, it appears that $a_n$ is sampling two periodic functions, perhaps in an aliased way (https://en.wikipedia.org/wiki/Aliasing). So maybe $a_n=f(n)=f_1(n)+f_2(n)$ or $a_n=f(n)=\cases{f_1(n)\quad n\in I_1\\f_2(n)\quad n\in I_2}$, where $f_1$ and $f_2$ have periods $T_1$ and $T_2$ that are irrational multiples (incommensurate) of each other.

To see this clearer, I decided to look at the plot of $(a_n,a_{n+1})$ instead, and we get:

And we can also see this in 3d, by plotting $(a_n,a_{n+1},a_{n+2})$, we get

and from another perspective

Why do I think $f_1$ and $f_2$ have incommensurate periods? If their periods are rational multiples, then I would expect to get one closed orbit, instead of two disjoint ones. Further, one of the periods of $f_1$ and $f_2$ must be irrational, otherwise we should get finitely many different points, rather than two "orbit filling" set of points (perhaps one calls this quasi-periodic? I recall Strogatz uses similar terminology in his non-linear dynamics text).

An example of this: Consider $a_n=\sin(n)+\sin(1+\pi n)$, a sum of two periodic functions with incommensurate periods, then $(a_n,a_{n+1},a_{n+2})$ gives plot

So what we have at hand then is some 3rd-order nonlinear discrete dynamical system, which I can only hope to learn more about. Similar to chaotic systems, the deterministic and boundedness nature are shared. Is there an analog "Lyapunov theory" for these discrete systems? I am not sure and would like to know more.

I have also looked at several variations:

(1) By adjusting the initial conditions $a_0,a_1,a_2$, they more or less affect the amplitudes, periods, and the vertical shifts of these functions. We still have two orbits.

(2) By considering $$a_{n+3}=\frac{a_{n+1}^{d}+a_{n+2}^{d}}{a_{n}}$$ with $a_{0}=a_{1}=a_{2}=1$ for some $d\ge 1$, they give similar behavior except the system seems to diverge without bound as $d>1.751$ experimentally. Here are some infima and suprema that I found experimentally: $\begin{array}{ccccccccccc} d & 1 & 1.1 & 1.2 & 1.3 & 1.4 & 1.5 & 1.6 & 1.7 & 1.75 & \ge1.751\\ \inf a_{n}\le & 0.81722 & 0.81921 & 0.82185 & 0.82173 & 0.82341 & 0.82750 & 0.81064 & 0.87859 & 0.65700 & 0\\ \sup a_{n}\ge & 5.1376 & 6.1357 & 7.7257 & 10.590 & 16.578 & 33.253 & 115.30 & 1984.7 & 176274.73198 & \infty \end{array}$ (The reason why I considered this variation was motivated from dynamical systems, where sometimes a parameter to the system will give a critical change in qualitative behavior. So $d$ has a criticality at around $1.751$ where the system is no longer bounded. Of course, this could also be due to computational limitations.)

(3) I have also looked at higher orders of the form $$a_{n+k}=\frac{a_{n+k-1}+\cdots+a_{n+1}}{a_n}$$, which all seems to give bounded sequence. The $k=4$ case experimentally I found $0.64568 \le a_n \le 17.22$.

This leads to two conjectures:

Conjecture 34. For a fixed integer $k\ge1$, the sequence $(a_{n})$ given recursively by $a_{n+k}=\frac{a_{n+1}+\cdots+a_{n+k-1}}{a_{n}}$ is always bounded for any choice of initial conditions $a_{0},\ldots,a_{k-1}$, provided that the sequence is defined for all $n$.

and

Conjecture 35. For a fixed integer $k\ge1$, the sequence $(a_{n})$ given recursively by $a_{n+k}=\frac{a_{n+1}+\cdots+a_{n+k-1}}{a_{n}}$ with initial conditions $a_{0}=\cdots=a_{k-1}=1$ is eventually not integral.

The integrality of this sequence was part of the (many) motivations of looking at these sequences, as they are superficially similar to the Somos sequences (https://en.wikipedia.org/wiki/Somos_sequence).

I can show in a specific simple case where these some of these terms obey periodicity:

Proposition 36. Given the order k type 1 sequence given by $a_{n+k}=\frac{a_{n+1}+a_{n+2}+\cdots+a_{n+k-1}}{a_{n}}$ with $a_{0}=-1$, and $a_{1},\ldots,a_{k-1}$ arbitrary. If ths seuqnece $a_{n}$ is defined for all n, then we have $a_{n}=-1$ for all $n$ that is a multiple of $k+1$.

Proof. Indeed, we have $a_{0}=-1$ and suppose $a_{j}=-1$ where $j$ is a multiple of $k+1$. Then note $$a_{j+k+1} =\frac{a_{j+2}+a_{j+3}+\cdots a_{j+k-1}+a_{j+k}}{a_{j+1}} =\frac{a_{j+2}+a_{j+3}+\cdots+a_{j+k-1}+\frac{a_{j+1}+\cdots a_{j+k-1}}{a_{j}}}{a_{j+1}} =\frac{a_{j+2}+a_{j+3}+\cdots+a_{j+k-1}-(a_{j+1}+\cdots a_{j+k-1})}{a_{j+1}} =\frac{-a_{j+1}}{a_{j+1}}=-1.$$

Though $a_{n}=-1$ for all n that is a multiple of $k+1$, the other terms need not observe periodicity. $\blacksquare$

If it is of interest to some of you: Some of these investigations are somewhat related to the study of cluster algebras (https://en.wikipedia.org/wiki/Cluster_algebra). A well known periodic sequence that arises from such "rational function" rule is the rule $$x_{n+1} = \frac{1+x_n}{x_{n-1}}$$ which has a perhaps surprising period of 5 (!). As it turns out, this "5" is no "accident", and is precisely the Catalan number "5". This particular "system" is a cluster algebra of rank 2. A rank 3 one has an orbit of 14, also a Catalan number.

In any case, perhaps this can start a conversation on this topic, as I am also stuck on this myself.