6

I was recently fooling around on my calculator, and found a recurrence relation that behaves very weirdly (it started looking like a mutilated combination of sine graphs at some points, presumably due to some sort oscillation due to the subtraction):

$$a_n=1-\dfrac{a_{n-1}}{a_{n-2}}, \qquad a_1 = a, \qquad a_2 = b$$

Is there any explicit (non-recursive) formula for $a_n$ in this recurrence relation? Or is it just not possible to find it? If it's not possible to find it, are there any values of $a$ and $b$ that allow for a solution (similarly to the logistic map)?

Also, if at all possible, would it be possible to show work for this monstrosity?

Rodrigo de Azevedo
  • 1
Adalynn
  • 335

2 Answers2

1

If you ever get two successive values that are equal you get division by zero in two more steps. You can't alternate between two values, because to go $a,b,a,b,\ldots$ you need $$a=1-\frac ba\\b=1-\frac ab\\a^2=a-b\\b^2=b-a$$ and one of the squares must be negative. I ran $500$ iterations for a few starting values. Each time I got a pair of values in the hundreds when two preceding values were very close. It looks quite chaotic.

If you allow the values to be complex, you can alternate between $1+i$ and $1-i$ but that seems to be an unstable equilibrium.

Ross Millikan
  • 374,822
  • If the sequence is undefined past a certain point, would one consider it to have an explicit formula? (not what I was looking for, though) – Adalynn Apr 18 '18 at 22:35
  • It is only undefined for some starting values. You can certainly find an explicit formulas for each of the $a_n$ but they quickly become a mess. I would be surprised if somebody finds a nice one for all $n$, but I have been surprised before. – Ross Millikan Apr 18 '18 at 22:39
  • I would be surprised if a messy one was found for all $n$! People can find surprising things when they're knowledgeable and determined. – Adalynn Apr 19 '18 at 00:43
1

To add yet another partial answer, there certainly is a fixed cycle of size 3. It starts with $(a,b)=(1.347296355333858, 2.5320888862379594)$, and seems to be unstable (that is, small deviations from it tend to grow). Worse yet, it seems to be unstable both ways: you may iterate backwards to find $a_0$, $a_{-1}$, $a_{-2}$ and so on, and still the small deviations will grow. Other than that, the backwards iteration is relatively well-behaved, in that it tends to converge after a brief period of chaos. Not that it helps us much, though.

Yes, I guess no explicit formula is to be found, and yes, this thing looks pretty much as chaotic as the logistic map (even though the latter does have an explicit formula at $r=4$). I guess there are fixed cycles of all sizes, and they all are unstable (otherwise we would have stumbled upon one by now).

Ivan Neretin
  • 12,835