# Periodic sequences given by recurrence relations

Question: Is there any sort of theory on periodic sequences given by recurrence relations? I cannot describe what makes the examples at the bottom interesting, or what I could possibly want to know about a general theory (if one exists). I hope they are more than just curiosities, but I cannot really tell where, in the mathematical world, they fit, or where I could go to learn anything about them.

What I know: (possibly a red herring, or running before crawling) To exclude sequences like $x \mapsto x + k \pmod p$ that are obviously periodic, the interesting examples I've seen so far have terms that are Laurent polynomials in the first two terms $a_1 = x$ and $a_2 = y$. This is even called the Laurent Phenomenon (I personally know very little about Laurent polynomials).

Based on my research (primarily Fomin and Reading's notes Root Systems and Generalized Associahedra and web searches), there are certain structures called cluster algebras (or, evidently, Laurent phenomenon algebras) that seem to have been created with these recurrence relations in mind, or as a motivation, or create them as a natural byproduct (I don't know).

Although I've taken some courses in combinatorics in which recurrence relations were covered, I really don't remember anything periodic happening, just the basic stuff (and I've forgotten most of that!).

Motivation: In this question, a sequence $a_i$ is given by the recurrence relation $a_i = a_{i - 1}a_{i + 1}$, or equivalently, $a_{i + 1} = \frac{a_i}{a_{i - 1}}$. It is shown in several answers that if $a_1 = x$ and $a_2 = y$, the terms of the sequence are

$$\underbrace{x,\, y,\, \frac{y}{x},\, \frac{1}{x},\, \frac{1}{y},\, \frac{x}{y}}_{\text{period}},\, x,\, y,\, \ldots$$

and so is periodic with period of $6$.

This reminded me of Fomin and Reading's notes Root Systems and Generalized Associahedra. The first topic there is a sequence defined recursively by \begin{align} f_1 &= x,\\ f_2 &= y, \\ f_{i+1} &= \frac{f_i + 1}{f_{i - 1}}, \end{align} whose terms are $$\underbrace{x,\, y,\, \frac{y+1}{x},\, \frac{x+y+1}{xy},\, \frac{x+1}{y}}_{\text{period}},\, x,\, y,\, \ldots$$

that turns out to have period $5$.

• And amusingly enough, in the first example ($f_{i + 1} = \frac{f_i}{f_{i - 1}}$), if your first terms are $\cos \theta$ and $\sin \theta$, the terms of the series cycle through the six trig functions! – pjs36 Apr 12 '17 at 15:08
• probably I am missing something but just in case... "periodic sequences given by recurrence relations" sounds to me like a discrete-time dynamical system (which indeed is a recurrence relation) that arrives, starting from a initial condition $(x_0,y_0)$ to a periodic $n$-orbit cycle attractor, which is stable and cyclic (so after some iterations of the recurrence formula, it arrives to a sequence of points, cyclically repeating the visit to those points in the same order). – iadvd Feb 19 '18 at 3:31
• correction: in your case the initial condition is a given $x_0$, not a couple $(x_0,y_0)$ as I said, but the rest of the comment is valid apart from that. – iadvd Feb 19 '18 at 3:55
• Is there a way to write the recurrence relation as a matrix? Similar to how the Fibonacci numbers can be computed by exponentiation of a matrix which encodes the relation. – Josh B. Feb 19 '18 at 4:38
• You may be interested in MSE question 1584296 which is a simple generalization of the Lyness 5-cycle which is quasiperiodic in general, and periodic for some initial conditions. – Somos Feb 22 '18 at 4:13

Following our conversation in the comments, "periodic sequences given by recurrence relations" is very close to the behavior of a discrete-time dynamical system (which indeed is a recurrence relation) that arrives, starting from a initial condition $x_0$ to a periodic $n$-orbit cycle attractor, in other words, a stable cycle of points, repeating the visit to those points in the same order.

Caveat: please if somebody can enhance my answer, any correction is welcomed.

As in your case you are working with a one-dimensional recurrence relation (aka map, aka discrete-time dynamical system), there is no chaos (it is required at least two dimensions to obtain a chaotic dynamical system), so no chaotic attractors will appear associated to the system, but you can arrive to sequences of points from which the recurrence formula cannot escape (it is the attractor). So the attractor would be your "periodic sequence".

For instance, the most famous case is the Logistic map, which is very useful to understand the basic concepts of the discrete-time maps:$$x_{n+1}=r \cdot x_n(1-x_n)$$

Where you can decide the initial condition $x_0$ of the system and you can decide the value of the control parameter $r$. Depending on the value of $r$ you will arrive to different stable $n$-orbit solutions. So some of them will arrive depending on the value of $r$ to a $2$-orbit cycle, $3$, $4$, many... or you never arrive to one, which is also possible depending on the definition of the dynamical system.

To see the whole picture of what happens when $r$ changes, you can study the bifurcation diagrams. They basically represent a graph in which the $x$-axis is one of the control parameters and in the $y$-axis you put the value of the $n$-orbit points where the specific $r$ case arrive. This leads to a graph where you can study the evolution of the system depending on the value of $r$. E.g. here is the bifurcation diagram of the Logistic map (credits to Wikipedia):

Another example: if we assume that the Collatz conjecture is true, then it behaves like a discrete-time dynamical system (in $\Bbb N$): it does not matter the initial condition $x_0$: you will arrive to the $3$-orbit $\{1,4,2\}$. Since the moment you arrive to $1$ you cannot escape from $\{1,4,2\}$.

• It is kind of similar, but not what the OP is asking about. As far as I understand the OP is asking about sequences which are periodic from the start and from any initial conditions. Edit reading the comments, I see now that the OP asked you for elaboration, so I see why this answer is useful – Yuriy S Feb 20 '18 at 8:13
• @YuriyS thanks for checking! yes as you said I decided to answer just after confirming the positive comment of the OP. – iadvd Feb 20 '18 at 8:19
• It does sound like the phenomenon I find interesting certainly fits into the purview of discrete time dynamical systems, but I think it may be a bit broad. – pjs36 Feb 20 '18 at 16:52
• @pjs36 indeed if you want to study families of recurrences, for instance, in your example instead of $a_{i+1}=\frac{a_i}{a_{i−1}}$ something more generic, like $a_{i+1}=k \cdot \frac{a_i}{a_{i−1}}, k \in \Bbb N$, and you want to know the behavior of the whole family depending on the value of $k$, then I would suggest this approach. – iadvd Feb 20 '18 at 23:42

The related question is finding functions such that their composition returns the argument: $$f(f(x))=x$$ Simple examples are: $$f(x)=1-x$$ $$f(x)=\frac{1}{x}$$ $$f(x)=\frac{1-x}{1+x}$$

They are called self-inverse functions, because by definition of inverse function:

$$f^{-1}(f(x))=x$$

A more general example:

$$f(x)=(1-x^a)^{1/a}$$

Self-inverse functions always give period $2$, but we can also search for functions such that: $$f(f(f(x)))=x$$ and so on. All of this allows for a 1st order recurrence relation to be periodic, instead of 2nd order which the OP provides.

A simple case of 1st order recurrence with period $N$ will be

$$z_{n+1}=z_n^{\omega_N}$$

where

$$\omega_N=\sqrt[N]{1} \neq 1$$

For example $\omega_3=e^{ \pm 2 \pi i/3}$ will give a recurrence with period $3$.

• I forgot about those linear fractional examples you give, with order $2$ -- those are good examples (however, I'm not quite as interested in the "exotic" $z_{n+1}$ example given; it's a little less surprising there's period behavior just around the bend, plus there are non-integers used). Basically, the examples I've liked feel like representations of cyclic/dihedral groups, but over some kind of vector space of rational functions. I don't think that's quite precise, but these suggestions have helped me realize this is the sort of thing that seems to be happening. – pjs36 Feb 20 '18 at 16:59

Here is something interesting. Define $\;a_n := f(n\; r)\;$ where $\;r\;$ is a constant, $\;f(x)=f(x+1)\;$ for all $x$,$\;f$ is a period $1$ function. If $\;r\;$ is rational then the sequence $\{a_n\}$ is purely periodic. If not, then the sequence is not periodic unless $\;f(x)\;$ is constant, but the function $\;f\;$ can be uniquely recovered from the sequence if $\;f\;$ is continuous, and even though $\{a_n\}$ is not periodic, still it is uniquely associated with the function $\;f\;$ which is periodic.

Generalized Somos sequences lead to such sequences. For example, let Somos-4 be defined by $$\;s_0=s_1=s_2=s_3=1\; \textrm{and} \;s_n = (s_{n-1}s_{n-3} + s_{n-2}s_{n-2})/s_{n-4}.\;$$ Now define the 2nd quotient sequence $a_n := (s_{n-1}s_{n+1})/(s_ns_n).\;$ Associated is the function $$\;f(x) := 1 - \wp(\omega_2(x-1/4)+\omega_1 + u)\;$$ where $\;u=.543684160\dots,\;r=.3789172825\dots,\;g_2=4,\; g_3=-1.\;$ The Weierstrass periods are $\;\omega_1=-2.451389\dots,\; \omega_2=2.993458\dots\;$ and we have that $a_n = f(n\; r)\;$ for all integers $\;n.\;$ The sequence satisfies $\;a_1\!=\!a_2\!=\!1,\; a_{n+1}\!=\!(a_n + 1)/(a_na_na_{n-1}).\;$ Compare to the Lyness 5-cycle.

The above example can be greatly generalized to produce interesting sequence defined by rational recurrence relations and which are associated with periodic functions. For example, Somos-5, Somos-6, Somos-7 sequences and their generalization also work when we use the 2nd quotient sequences of them. Note that it is not immediately obvious that the associated functions $f$ exist. Note also that the sequences all satisfy the Laurent phenomenon -- an unexpected property.

Unlike the special cases $\;a_n=a_{n-1}/a_{n-2}\;$ and $\;a_n=(a_{n-1}+1)/a_{n-2}\;$ which are purely periodic, these generalized sequences are associated with functions $f$ where $r$ depends on the initial values of the sequence and only periodic if $r$ is rational. For a very good example of this please read MSE question 1584296 about generalizing these two special cases, and which I also answered.

Finally, if you have time, you may be interested in the Ph.D. Thesis of Jonny Griffiths, Lyness Cycles, Elliptic Curves, and Hikorski Triples which goes into a lot of details, has proofs, references, a wide range of topics, and gives elementary examples such as a 10-cycle and 12-cycle.

• I tried to compute the example sequence $a_n$, then quickly ran to Sage for a bit of help. I've either misunderstood your answer (that $a_n$ should be periodic for these initial conditions), computed incorrectly, or haven't gathered enough terms, because I haven't seen a period yet, going up to 40 terms. [1, 1, 2, 3/4, 14/9, 69/49, 413/529, 7222/3481, 90211/98596,... – pjs36 Feb 25 '18 at 18:45
• @pjs36 You computed correctly. $a_n$ is not periodic but closely associated with $f$ which is. I added the emphasis for this. If $r$ was rational, then $a_n$ would be periodic. – Somos Feb 25 '18 at 20:14
• Ah, I see; thank you for the clarification. – pjs36 Feb 25 '18 at 20:38

This is mainly a consideration more then an answer, but could be useful in discussing this interesting subject.

It is known that there are "similarities" in the solutions to Ordinary Differential Equations (ODE) and to Finite Difference Equations (FDE).
Actually, FDE can be used, under proper conditions, to compute approximated solutions to the ODE.

Since a recurrence is essentially a FDE, than a FDE that mimicks a ODE that admits periodic solutions might also give a periodic solution, with appropriate initial conditions.

Therefore, as an example of linear equations, to $$y''+y=0\quad \to \quad y(x)=A \sin{x+\phi}$$ we can associate a slight different FDE $$\Delta ^{\,2} y(n) + \Delta y(n) + y(n) = y(n + 2) - y(n + 1) + y(n) = 0\quad \to \quad y(n) = A\cos \left( {n{\pi \over 6} + \alpha } \right)$$

We have in fact \eqalign{ & y(n) = A\cos \left( {n{\pi \over 6} + \alpha } \right) = A\left( {\cos \alpha \cos \left( {n{\pi \over 6}} \right) - \sin \alpha \sin \left( {n{\pi \over 6}} \right)} \right) \cr & \Delta y(n) = A\left( { - \left( {{{\cos \alpha + \sqrt 3 \sin \alpha } \over 2}} \right)\cos \left( {n{\pi \over 6}} \right) + \left( {{{\sin \alpha - \sqrt 3 \cos \alpha } \over 2}} \right)\sin \left( {n{\pi \over 6}} \right)} \right) \cr & \Delta ^{\,2} y(n) = A\left( {\left( {{{ - \cos \alpha + \sqrt 3 \sin \alpha } \over 2}} \right)\cos \left( {n{\pi \over 6}} \right) + \left( {{{\sin \alpha + \sqrt 3 \cos \alpha } \over 2}} \right)\sin \left( {n{\pi \over 6}} \right)} \right) \cr & \Delta ^{\,3} y(n) = y(n) \cr} so that we could also use $$\Delta ^{\,3} y(n) = y(n)$$

For non-linear equations "similarities" are quite less straight but ODEs can provide an indication.

The disciplines of Digital Signal Processing and of Dynamical Systems provide various tools to analize the response of circuits in the dicrete time domain, which are the practical realization of recurrent relations. Included are the mathematical tools to parallel the discrete time and continuous time behaviour, Laplace and z-Transforms for instance (refer to this Wikipedia article for starting and look for references).

In summary, all the linear and non-linear physical models that provides an oscillating or resonating behaviour will translate into homogeneous or non-homogeneous ODEs and FDEs whose solutions include periodic continuous or discrete functions: a simple or double pendulum, a ball in a bowl of any convex shape, a particle in a gravitational field, an acoustic or EMW resonator, etc.
And finally, to mention an intrinsically discrete time oscillator, consider any system governed by a periodic Markov chain.

• Great explanation! – jfkoehler Feb 25 '18 at 23:01
• @jfkoehler: glad for your appreciation. – G Cab Feb 25 '18 at 23:39
• Ah, my avoidance of ODEs yet again comes back to bite me :) I'll have to look into this sort of thing, thank you! – pjs36 Feb 26 '18 at 0:44
• Any good references for works that bridge the finite and continuous with recurrence and Diff EQs? – jfkoehler Feb 26 '18 at 1:07
• @jfkoehler: I added to my answer a reference to Wikipedia article on the subject, from where you can start and look for interesting works. – G Cab Feb 26 '18 at 10:10

The classic example of that periodic sequence is the periodic part of the quotents sequence in the Euclidean algorithm for a square irrationals in the form of $$x_{n+1} = \frac 1{x_n - [x_n]},$$ where $$x_n = \frac{a_n\sqrt M + b_n}{d_n},\tag1$$ because every square irrational can be presented as periodic continued fraction.

At the same time, this recurrent relation generates periodic natural sequences $a_n, b_n, d_n$ and $c_n= [x_n],$ because $$x_{n+1} = \dfrac1{\dfrac{a_n\sqrt M + b_n}{d_{n}} - c_n} = \frac {d_n}{a_n\sqrt M + b_n - c_nd_n} = \dfrac{a_n\sqrt M + c_nd_n - b_n}{a_n^2M -(b_n - c_nd_n)^2}$$ also can be presented in the form (1).

Suppose you have a sequence of distinct elements $b_0,\ldots,b_{n-1}$ and let

$$a_{k+1} = \sum_{i = 0}^{n-1} b_{i+1} \prod_{j\neq i}\frac{a_k - b_j}{b_i - b_j}.$$

Note that if we have $a_k = b_i$, all terms in the sum vanish except the one for $b_{i+1}$, where the product is just 1, so $a_{k+1} = b_{i+1}$. This shows that if we set $a_1 = b_1$, the sequence will be periodic with terms $b_0,\ldots,b_{n-1}$.

The RHS of the recurrence relation is a degree $n-1$ polynomial in $a_k$. Perhaps this characterizes these sequences?

The idea comes from Lagrange interpolation.

• This is interesting, thank you -- I'll definitely have to play around with some examples. I guess we'd need as many initial conditions as the period, it looks like. – pjs36 Feb 26 '18 at 0:51
• No it’s just the one initial condition $a_1 = b_1$. The rest are encoded in the equation itself. It’s 1st order. – Alexander Vlasev Feb 26 '18 at 4:32