Investigating the recurrence relation $x_{n+1}=\frac{x_{n}+x_{n-1}}{(x_{n},\,x_{n-1})}+1$

Question

Let $x_{n} \in \mathbb Z$ be the $n$-th term of the recurrence relation

$$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + 1$$

where $(x_{n},x_{n-1})$ is the gcd of $x_{n}$ and $x_{n-1}$.

Some examples:

• $1, 1, 3, 5, 9, 15, 9, 9, 3, 5, 9, 15,\dots \qquad $ (periodic sequence)

• $1, 12, 14, 14, 3, 18, 8, 14, 12, 14, 14, 3, \dots \qquad$ (periodic sequence)

• $3, 1, 5, 7, 13, 21, 35, 9, 45, 7, 53, 61, 115, 177, 293, 471, 765, 413, \dots \qquad$ (not periodic?)

If $x_{0}$ is even or $x_{1}$ is even, the sequence seems to be always periodic: how to prove it?

More difficult, I suppose, is to predict the character of the sequence (periodic or not periodic), given its initial values $x_{0}$ and $x_{1}$.

---

Addendum

The recurrence relation

$$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + 3$$

admits the following periodic sequence (period equal to 81):

$2, 5, 10, 6, 11, 20, 34, 30, 35, 16, 54, 38, 49, 90, 142, 119, 264, 386, 328, 360, 89, 452, 544, 252, 202, 230, 219, 452, 674, 566, 623, 1192, 1818, 1508, 1666, 1590, 1631, 3224, 4858, 4044, 4454, 4252, 4356, 2155, 6514, 8672, 7596, 4070, 5836, 4956, 2701, 7660, 10364, 4509, 14876, 19388, 8569, 27960, 36532, 16126, 26332, 21232, 11894, 16566, 14233, 30802, 45038, 37923, 82964, 120890, 14564, 6160, 474, 3320, 1900, 264, 544, 104, 84, 50, 70, 15, 20, 10, 6, 11, 20, \dots$

The recurrence relation

$$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + 17$$

with $x_0=1$ and $x_1=4$ produces the following periodic sequence (period equal to 422):

The recurrence relation

$$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + 199$$

with $x_0=1$ and $x_1=2$ produces the following periodic sequence (period equal to 2920):

---

I made some numerical experiments. The following screenshots show some of the obtained results.

Each image consists of a 20x20 matrix $T(c)$, depending on the value of $c$, in which

• $x_0$ is the row index;
• $x_1$ is the column index;
• $t_{\,x_0,\,x_1}(c)$ represents the period of the sequence generated by the recurrence relation starting with the initial conditions $x_0,\,x_1$ (the symbol "+" stands for a not periodic sequence that diverges).

Results for $\,c=1$:

Results for $\,c=2$:

Results for $\,c=3$:

Results for $\,c=4$:

Results for $\,c=5$:

Here it seems that we have only two possible periods: one of lenght 17, the other of lenght 63. Notice that if we focus on the sequences of period equal to 17 and plot them for the following initial values $(x_0,x_1)=(2,2),\,(3,8),\,(7,12)$, we obtain the same "wave form"!

I conjecture that this fact is always true.

The wave form for the period of lenght 63 is completely different:

• for $(x_0,x_1)=(3,10)$ we have

• for $(x_0,x_1)=(13,6)$ we have

Results for $\,c=6$:

Results for $\,c=7$:

Results for $\,c=8$:

Results for $\,c=9$:

Results for $\,c=10$:

Results for $\,c=11$:

Results for $\,c=13$:

Results for $\,c=15$:

Results for $\,c=17$:

Results for $\,c=19$:

Answer 1

Alright, I finally managed to "prove" the case when at least one of $x_0$ and $x_1$ is even and you add an odd integer after the division. I say "prove" as this is really a heuristic argument but it is still pretty interesting nonetheless and might illuminate a way forward.

Define the sequence

$$x_{n+2}=\frac{x_{n+1}+x_n}{\gcd(x_{n+1},x_n)}+s$$

where at least one of $x_0$ and $x_1$ is even and $s$ is odd. It is obvious that to prove that the sequence is periodic it is sufficient to show that it is bounded as there are only a finite number of pairs $(x_{n+1},x_n)$ that define the term $x_{n+2}$. Starting with a pair of integers with parity $(E,O)$ (that is, $x_n$ is even and $x_{n+1}$ is odd) it is easy to show by induction that

$$(E,O)\to (O,E)\to (E,E)$$

That is, we get that both $x_{n+2}$ and $x_{n+3}$ is even. But what about $x_{n+4}$? At this point, we have $x_{n+4}$ is odd if $x_{n+3}=2^qa$ and $x_{n+2}=2^qb$ for some odd $a$ and $b$. Otherwise, $x_{n+4}$ will be even. Thus $(E,E)\to (E,O)$ or $(E,E)\to (E,E)$. At this point, this is all I can concretely say about this problem and now move to the heuristics.

Quick Definition: As an aside, from here on out when I say "the probability" that an integer has a certain property $\chi$ I mean

$$P(\chi)=\lim_{n\to\infty}\frac{\left|\{z\in\{1,2,...,n\}:z\text{ has property }\chi\}\right|}{n}$$

Heuristic $1$: What is the probability that $(E,E)\to (E,O)$ versus $(E,E)\to (E,E)$. Well, for to large even integers $x=2^pa$ and $y=2^qb$ (WLOG assume $p\geq q$) we have

$$\frac{x+y}{\gcd(x,y)}+s=\frac{2^{p-q}a+b}{\gcd(a,b)}+s$$

This sum is odd if and only if $2^{p-q}a$ is odd. But for large integers, the probability that a number is odd is $\frac12$. Thus, the probability that $(E,E)\to (E,O)$ versus $(E,E)$ is $\%50$. Now, a quick discussion on why this is an acceptable heuristic. Basically, in order to show that the sequence is bounded it is better if $(E,E)$ leads to $(E,E)$ versus $(E,O)$. In fact, just looking at some randomly generated data it appears that $(E,E)\to (E,E)$ more frequently than not. However, this is fine as the $\frac12$ mark can really just be thought of as an upper bound (even if we had to hand wave to get it). If it isn't quite the correct number, I feel confident that it is an upper bound since we didn't take into account any structure of the problem when considering if $2^{p-q}a$ (from above) was odd or not.

Heuristic $2$: What is the expected value of the $x_{n+2}$ if $(x_n,x_{n+1})=(E,E)$? From here we can say that the probability that two numbers $x$ and $y$ have a specific greatest common divisor $k$ is

$$P(\gcd(x,y)=k)=\frac{1}{k^2\zeta(2)}$$

Thus, the expected value of $\frac{x_{n+2}}{\max(x_n,x_{n+1})}$ is

$$E(x_{n+2})\leq 2\sum_{n=1}^\infty \frac{P(\gcd(x_n,x_{n+1})=2n)}{2n}=\frac{2}{\zeta(2)}\sum_{n=1}^\infty \frac{1}{(2n)^3}=\frac{\zeta(3)}{4\zeta(2)}$$

Call this value $E(E)$.

Heuristic $3$: What is the expected value of the $\frac{x_{n+2}}{\max(x_n,x_{n+1})}$ if $(x_n,x_{n+1})=(E,O)$ or $(O,E)$? In the same manner as above, we have

$$E(x_{n+2})\leq 2\sum_{n=1}^\infty \frac{P(\gcd(x_n,x_{n+1})=2n-1)}{2n-1}=\frac{2}{\zeta(2)}\sum_{n=1}^\infty \frac{1}{(2n-1)^3}=\frac{7\zeta(3)}{4\zeta(2)}$$

Call this value $E(O)$.

Heuristic $4$: Using Heuristic $1$ above, we know that half the time our sequence would trace the following

$$(E,E)\to (E,O)\to (O,E)\to (E,E)$$

If we start at $x_n$ and $x_{n+1}$, then the expected value of of the sequence member divided by $\max(x_n,x_{n+1})$ the next time we hit $(E,E)$ (denoted by $x_t$) is bounded by

$$E(x_{t}|(E,O))\leq E(E)E(O)^2$$

On the other hand, if $(E,E)\to (E,E)$ then we have $E(x_{t}|(E,E))=E(E)$. Putting these together gives us

$$E(x_t)=\frac{E(x_{t}|(E,O))+E(x_{t}|(E,E))}{2}$$

$$=\frac{1}{8}\left(\frac{49}{16}\cdot\left(\frac{\zeta(3)}{\zeta(2)}\right)^3+\frac{\zeta(3)}{\zeta(2)}\right)<\frac{1}{4}$$

Basically, by the time $(E,E)$ shows up again, we would expect the sequence member to be on average a quarter the size.

Addendum: As an addendum, here is a discussion on why this method would not work for the starting case $(O,O)$. In this case, it is obvious that we simply go $(O,O)\to (O,O)$. But then we would have

$$E(x_t)=E(O)=\frac{7\zeta(3)}{4\zeta(2)}=1.27>1$$

Thus, for large integers on average you would expect the sequence to increase in size. Again, this isn't a proof and there clearly are cases where all odd sequences can be periodic. However, it seems much more random to try to show when these cases arise.