# Finding the limit of a nonlinear recursion sequence as $n$ goes to ∞

I want to find the limit as n goes to infinity of the nonlinear recursion sequence

x[n + 1] = x[n]/x[n - 1], x[-1] = 2, x[0] = 8]


eqn = {x[n + 1] == x[n]/x[n - 1], x[-1] == 2, x[0] == 8};


Using RSolve

soln = RSolve[eqn, x, n] // FullSimplify // Quiet;


Verifying that the solutions satisfy the equation and boundary conditions

eqn /. soln // FullSimplify

(*  {{True, True, True}, {True, True, True}}  *)


Only the first solution is real-valued

ComplexExpand[x[n] /. soln] // FullSimplify


Clear[solnR]

solnR[n_] = x[n] /. soln[[1]] // ComplexExpand // Simplify;


The min and max values are

{min, max} = (pts = {n, solnR[n]} /.
Solve[{solnR'[n] == 0, -5 < n < 20}, n, Reals] // FullSimplify)[[All,
2]] // Union

(*  {4^(-Sqrt[7/3]), 4^Sqrt[7/3]}  *)

{min, max} // N

(*  {0.12032, 8.31116}  *)

pts[[All, 1]] // SortBy[#, N] & // Differences // FullSimplify

(*  {3, 3, 3, 3, 3, 3, 3}  *)


Hence, the function is periodic with a period of 6. Verifying,

solnR[n] == solnR[n + 6] // FullSimplify

(*  True  *)

Plot[solnR[n], {n, -5, 20},
Epilog -> {Red, AbsolutePointSize[6],
Point[pts]}]


So the limit is the interval

Interval[{min, max}]

(*  Interval[{4^(-Sqrt[7/3]),
4^Sqrt[7/3]}]  *)


For convenience, let's translate the sequence to start from n = 1:

sol = x[n] /.
RSolve[{x[n + 1] == x[n]/x[n - 1], x[1] == 2, x[2] == 8}, x[n], n][[1]] // FullSimplify


The limit is undefined, and falls into an Interval:

lim = Limit[sol, n -> Infinity]


Evaluating the first 10 values of sol:

Table[sol /. n -> m, {m, 1, 10}]


{2, 8, 4, 1/2, 1/8, 1/4, 2, 8, 4, 1/2}

yields the same numbers as

RecurrenceTable[{x[n + 1] == x[n]/x[n - 1], x[1] == 2, x[2] == 8},  x[n], {n, 1, 10}]


Plotting the first 100 values obtained via RecurrenceTable:

shows 6 regularly alternating values. Hence, there is no limit in infinity for this recursive relation.