Behaviour of $u_{n}=\frac{u_{n-1}+u_{n-2}+n}{\gcd\left(u_{n-1},u_{n-2},n\right)}$

Question

Let $u_1=u_2=1$ and
$$u_{n}=\frac{u_{n-1}+u_{n-2}+n}{\gcd\left(u_{n-1},u_{n-2},n\right)}$$ Then I suspect that $$\lim_{n\rightarrow\infty}\frac{u_{n+1}}{u_{n}}=\frac{1+\sqrt{5}}{2}$$ which is equivalent to the fact that $\gcd\left(u_{n-1},u_{n-2},n\right)=1$ for $n$ large enough.

It seems that this property holds for any starting integer values $(u_1,u_2)$. Does anyone see how to prove it?

Proof of the equivalence. If $\lim_{n\rightarrow\infty}\frac{u_{n+1}}{u_{n}}=\frac{1+\sqrt{5}}{2}=\phi$ and since we have $\frac{n}{u_{n-1}}\rightarrow0$ then we get

$$\frac{1+\frac{u_{n-2}}{u_{n-1}}+\frac{n}{u_{n-1}}}{\gcd\left(u_{n-1},u_{n-2},n\right)} \sim\frac{1}{\gcd\left(u_{n-1},u_{n-2},n\right)}\left(1+\frac{1}{\varPhi}\right)\sim\varPhi\ \left(n\rightarrow\infty\right)$$

and necessarily we have $\gcd\left(u_{n-1},u_{n-2},n\right)\rightarrow1$. Since it is an integer value it must be $1$ for $n$ large enough.

In the other way if $\gcd\left(u_{n-1},u_{n-2},n\right)=1$ for $n>n_{0}$ then we have for $n>n_{0}$

$$u_{n}=u_{n-1}+u_{n-2}+n$$

and $u_{n}=a\varPhi^{n}+b\varPhi^{-n}+cn+d$ for some constants $(a,b,c,d)$ with $a>0$.

I add that if we replace $n$ with a function $f(n)$ sufficiently regular like $f(n)=n^2$ i.e. $u_{n}=\frac{u_{n-1}+u_{n-2}+f(n)}{\gcd\left(u_{n-1},u_{n-2},f(n)\right)}$ the property seems to persist.

Thank you

ps: here the values of $n$ such that $\gcd\left(u_{n},u_{n-1},n+1\right)>1$ and the corresponding gcd. No gcd>1 after $n=22933$ until $n=10^6$

(5,5),(6,2),(9,3),(12,2),(27,3),(48,3),(69,3),(90,3),(111,3),(135,3),(159,3),(165,3),(171,3),(177,3),(183,3),(204,3),(225,3),(249,3),(270,3),(273,7),(291,3),(300,5),(306,17),(327,3),(333,3),(357,21),(363,3),(369,3),(393,3),(399,3),(420,3),(426,3),(430,5),(447,3),(471,3),(495,3),(519,3),(525,3),(546,3),(570,3),(594,9),(618,3),(624,3),(645,3),(669,3),(690,3),(714,3),(738,3),(744,3),(750,15),(771,3),(777,3),(801,3),(807,3),(820,5),(834,3),(840,3),(864,3),(885,3),(891,3),(897,3),(903,3),(924,3),(945,3),(951,3),(960,5),(972,9),(993,3),(1017,3),(1038,3),(1059,3),(1075,5),(1080,3),(1095,5),(1116,3),(1122,3),(1143,9),(1167,3),(1191,3),(1212,3),(1236,3),(1242,3),(1248,3),(1260,5),(1278,3),(1280,5),(1358,7),(1428,7),(1444,19),(16781,173),(16800,3),(16806,3),(16808,11),(16814,7),(16830,15),(16836,3),(16857,3),(16863,3),(16870,5),(16890,3),(16911,3),(16932,3),(16953,3),(16977,3),(17001,3),(17007,3),(17028,33),(17034,3),(17050,5),(17055,3),(17061,3),(17067,3),(17073,3),(17079,3),(17103,3),(17109,3),(17130,3),(17136,9),(17160,3),(17166,3),(17175,5),(17178,7),(17187,3),(17195,5),(17208,3),(17220,5),(17221,17),(17241,3),(17262,3),(17286,3),(17300,5),(17304,3),(17325,3),(17331,3),(17355,3),(17376,3),(17400,3),(17424,3),(17445,3),(17466,3),(17487,3),(17511,3),(17532,3),(17538,3),(17544,3),(17550,3),(17556,3),(17562,3),(17586,9),(17610,3),(17616,3),(17622,3),(17628,3),(17633,7),(17652,3),(17673,3),(17685,5),(17697,3),(17718,3),(17725,5),(17733,3),(17754,3),(17766,7),(17775,3),(17790,5),(17810,5),(17811,3),(17835,3),(17856,3),(17862,3),(17868,3),(17892,3),(17898,3),(17919,3),(17940,3),(17961,3),(17967,3),(17988,3),(17994,3),(18015,3),(18039,3),(18063,3),(18081,7),(18084,3),(18108,3),(18125,5),(18132,3),(18138,3),(18162,3),(18164,19),(18168,3),(18189,3),(18195,3),(18201,3),(18225,3),(18249,3),(18273,3),(18279,3),(18300,3),(18321,3),(18340,7),(18342,3),(18348,3),(18354,3),(18368,7),(18378,3),(18402,3),(18408,3),(18414,3),(18435,3),(18441,3),(18465,3),(18471,3),(18480,5),(18492,3),(18498,3),(18515,5),(18522,3),(18528,3),(18535,5),(18555,3),(18561,3),(18565,5),(18582,3),(18606,3),(18615,5),(18618,3),(18642,3),(18648,3),(18654,3),(18660,3),(18681,3),(18702,3),(18723,3),(18729,3),(18750,3),(18774,9),(18798,3),(18810,5),(18828,3),(18849,3),(18870,3),(18876,3),(18882,3),(18906,3),(18912,3),(18918,3),(18924,3),(18928,7),(18948,3),(18972,3),(18978,3),(18999,3),(19020,3),(19026,9),(19032,3),(19038,3),(19059,3),(19080,3),(19086,3),(19103,7),(19110,3),(19115,5),(19128,3),(19134,3),(19140,3),(19164,3),(19170,3),(19176,3),(19182,3),(19206,9),(19227,3),(19248,3),(19254,3),(19275,3),(19285,7),(19296,3),(19320,3),(19341,3),(19347,3),(19353,3),(19359,3),(19360,5),(19365,3),(19386,3),(19392,3),(19413,3),(19419,3),(19425,3),(19446,3),(19467,3),(19473,3),(19479,3),(19485,3),(19506,3),(19515,5),(19527,3),(19548,3),(19558,7),(19569,3),(19575,3),(19596,3),(19602,3),(19626,3),(19635,11),(19647,3),(19653,3),(19659,3),(19665,3),(19669,13),(19671,3),(19677,3),(19698,3),(19715,5),(19725,3),(19746,3),(19752,3),(19776,3),(19782,3),(19788,3),(19809,3),(19830,3),(19851,3),(19872,3),(19896,3),(19920,3),(19935,5),(19953,3),(19959,3),(19965,5),(19968,3),(19989,3),(20013,3),(20034,3),(20058,3),(20064,3),(20085,3),(20106,3),(20125,5),(20127,3),(20148,3),(20154,3),(20175,3),(20199,3),(20220,3),(20244,3),(20268,3),(20274,3),(20295,3),(20316,3),(20322,3),(20328,3),(20334,3),(20355,3),(20376,3),(20382,3),(20390,5),(20406,3),(20412,3),(20418,3),(20442,3),(20460,11),(20481,3),(20487,3),(20493,3),(20499,3),(20523,3),(20544,3),(20550,3),(20571,3),(20577,3),(20583,3),(20604,3),(20610,3),(20634,3),(20658,3),(20679,3),(20700,3),(20721,3),(20727,3),(20748,3),(20769,3),(20790,9),(20796,3),(20817,3),(20838,3),(20846,7),(20862,3),(20883,3),(20907,3),(20913,3),(20919,3),(20925,5),(20928,3),(20952,3),(20958,3),(20982,3),(21006,3),(21020,5),(21027,3),(21028,7),(21035,5),(21048,3),(21054,3),(21060,3),(21084,21),(21105,3),(21129,3),(21153,3),(21159,3),(21165,3),(21171,3),(21192,3),(21213,3),(21230,5),(21237,3),(21243,3),(21264,3),(21270,15),(21291,3),(21312,3),(21333,3),(21339,9),(21345,3),(21351,3),(21357,3),(21378,3),(21399,21),(21420,3),(21425,5),(21438,3),(21462,3),(21476,7),(21483,3),(21500,5),(21510,3),(21534,3),(21555,3),(21576,3),(21595,7),(21597,3),(21621,3),(21630,7),(21642,3),(21648,3),(21654,3),(21660,3),(21665,5),(21666,3),(21687,3),(21708,3),(21714,3),(21720,3),(21725,5),(21735,23),(21750,3),(21756,3),(21762,3),(21783,3),(21807,3),(21828,3),(21852,3),(21876,3),(21880,5),(21900,3),(21924,3),(21930,3),(21945,11),(21963,3),(21984,3),(21990,3),(22005,5),(22026,3),(22047,3),(22071,3),(22077,3),(22083,3),(22089,3),(22100,5),(22104,3),(22125,3),(22146,3),(22170,3),(22180,5),(22191,3),(22197,3),(22203,3),(22209,3),(22220,5),(22224,3),(22245,3),(22269,3),(22280,5),(22284,3),(22305,3),(22326,3),(22332,3),(22341,11),(22353,3),(22359,3),(22365,9),(22386,3),(22407,3),(22417,29),(22428,9),(22434,3),(22435,7),(22455,3),(22461,3),(22467,3),(22473,3),(22494,3),(22500,3),(22521,3),(22527,3),(22535,5),(22548,3),(22554,7),(22572,3),(22593,3),(22603,7),(22614,3),(22638,3),(22659,3),(22680,3),(22686,3),(22710,3),(22734,3),(22755,3),(22765,5),(22776,3),(22797,3),(22821,3),(22827,7),(22835,5),(22842,3),(22848,3),(22855,5),(22875,3),(22880,11),(22932,7)

Answer 1

The property probably does not hold.

An argument can be made that the property is unlikely to hold. Define $d_n = \gcd(u_{n-1},u_{n-2},n)$, $d_{\infty}=1$ and pick $N$ s.t. $d_{N-1} = 1$. Let $M$ be the smallest integer such that $d_{M} \neq 1, M\geq N$ or $M=+\infty$ if no such integer exists. For $n=N$ define $$a_n = 2 + 3n/2 + u_{n-2} + u_{n-1}/2,\\ b_n = 1 + n/2 + u_{n-1}/2. \tag{1}$$ We assume that the numbers $a_n$ and $b_n$ are integers with even $a_n + b_n$. For $u_1=u_2=1$ this assumption holds starting from $n=14$; if it does not hold, we can check that $2$ will divide $d_n$ within 6 iterations.

For $n>N$ define $a_n$ and $b_n$ by the recursive relation $$\begin{pmatrix}a_{n}\\b_{n}\end{pmatrix} = \frac12 \begin{pmatrix} 1 & 5\\ 1 & 1 \end{pmatrix}\begin{pmatrix}a_{n-1}\\b_{n-1}\end{pmatrix}.\tag{2}$$ It is easy to check that then equations (1) hold for $N \leq n \leq M$ and not only for $n=N$. Define

$$\widetilde{d}_n = \gcd(a_n-2, b_n-1). \tag{3}$$

Lemma 1.

1. If $p \mid d_M, p\notin \{2\}$ then $p \mid \widetilde{d}_n$,
2. If $p \mid \widetilde{d}_n, p\notin \{2,5\}$ then $M < \infty$.

Proof. #1 follows from $p\mid n$, $p\mid u_{n-1}$, $p\mid u_{n-2}$ and the formulas (1).

To prove #2 assume the contrary: $M=\infty$. Then (1) hold for all $n\geq N$. Define the field $F$ by $F=\text{GF}(p)$ when $\sqrt{5} \in \text{GF}(p)$ (i.e. when $p\equiv\pm 1 \mod 5$) and $F=\text{GF}(p)[\sqrt{5}]$ otherwise. In both cases $u_{\pm} = \frac{1\pm\sqrt{5}}{2} \in F$. Define $v_{\pm} = \frac{a_{N} \pm b_{N}\sqrt{5}}{2 \pm \sqrt{5}}\in F$. Let $\text{order}(u_{\pm})$ be the multiplicative order of $u_{\pm}$. It divides $p^2-1$ and, hence, $\text{lcm}_{\pm}(\text{order}(u_{\pm}))$ is coprime with $p$. We have $p\mid \widetilde d_n$ iff $u_{\pm}^{n-N}v_{\pm} = 1$ for both choices of $\pm$. If $n_0$ is the first such integer, then for $n=n_0+k\;\text{lcm}_{\pm}(\text{order}(u_{\pm}))$ also satisfies $p\mid \widetilde d_n$ for any non-negative integer $k$. Since $\text{lcm}_{\pm}(\text{order}(u_{\pm}))$ is coprime with $p$ we can pick $k$ such that $p\mid n_0 + k\;\text{lcm}_{\pm}(\text{order}(u_{\pm}))$. Then $p\mid d_n$.$\;\;\square$

Let's now estimate the likelihood that there is no $p,n$ s.t. $p\mid \widetilde d_{n}, p \notin \{2,5\}$ (which is required from Lemma 1 for $M=\infty$).

Conjecture 1. There is a positive density of primes $p$ s.t. $r \geq p-1$, where $r = \gcd_{\pm}(\text{order}(u_{\pm}))$.

Note 1.1. For $p\equiv \pm 1\mod 5$ we have $r\mid (p-1)$. For $p \equiv \pm2 \mod 5$ we have $r\mid (2p+2)$. Indeed

$$\left(\frac{1+\sqrt{5}}{2}\right)^{p} = \frac{1-\sqrt{5}}{2},$$ $$\left(\frac{1+\sqrt{5}}{2}\right)^{p+1} = -1,$$ $$\left(\frac{1+\sqrt{5}}{2}\right)^{2p+2} = 1.$$

Thus, the condition $r \geq p-1$ is equivalent to $r=p-1$ when $p\equiv \pm 1\mod 5$ and $r=2p+2$ when $p\equiv \pm2\mod5$.

Note 1.2. If one were to try to prove conjecture 1, methods in Kurlberg, Pomerance "On a problem of Arnold: The average multiplicative order of a given integer" could be useful. There is a related open problem "Artin's conjecture on primitive roots".

---

Non-rigorous speculation part

There is no easy way to talk about likelihoods of mathematical statements. In most cases they are either true or false. E.g. we can say that the probability the digit $9$ occurs more than $10^5$ times in the first $10^6$ digits of $\pi$ is about $0.5$, but in fact one can check the digits of $\pi$ and deduce that probability to be either $0$ or $1$. Yet, sometimes that sort of speculation is helpful to decide our confidence in facts which are not easy to check.

Given that setting, for $r \geq p-1$ we can speculate that for $p\equiv \pm 2 \mod 5$ the element $v_{+}$ is one of $p^2$ possible elements of $\text{GF}(p)[\sqrt{5}]$, and $2p+2$ of them lie on the orbit of $u_{+}$. Thus, there is roughly $\frac{2p+2}{p^2} > \frac{1}{p}$ probability that $v_{+}$ lies on the orbit of $u_{+}$. For $p \equiv \pm 1 \mod 5$ two conditions need to hold: $u_{+}^m = v_{+}$ and $u_{-}^m = v_{-}$ for the same $m$. Under the assumption $r=p-1$ the first of them determines a unique $m$ unless $v_{+}=0$, hence we estimate the likelihood they both hold at the same time as $\frac{p-1}{p^2} = \frac{1}{p} + o(1)$. Assuming these likelihoods to be independent for different $p$ and denoting the density of the primes satisfying conjecture 1 as $C$ and using the density of primes we get

$$\left(\text{Likelihood of $M = \infty$}\right) \leq \prod_{p\in\text{Primes}\setminus\{2,5\}}\left(1-\frac{C(1+o(1))}{p}\right) \\ = \exp\left(-C\int_{5}^\infty \frac{1+o(1)}{n\ln(n)}dn\right) = 0,$$

because the integral in the exponent diverges. The divergence is slow (as $C\ln\ln n$), hence, although the above argument suggests that a prime $p$ s.t. $p\mid \widetilde d_n$ is very likely to exist, it could be very large. E.g. this argument suggests that if we know that there are no such $p < 10^6$, and $C=0.5$ then one would need to search up to $p \simeq 10^{2400}$ if we want the above bounds to "guarantee" a $95\%$ confidence to find such $p$. If we do a more careful estimate instead of the bounds, effective $C$ could be higher, putting an estimate at around $p\simeq 10^{120}$ ($\pm$ a few dozen orders of magnitude) to "guarantee" the same confidence. I don't know any feasible way to do that.