Is there an easy way to see that this simple recurrence is 9-periodic?

Question

In a colloquium talk yesterday, Robert Bryant pointed out that for all initial values $a_0, a_1 \in \mathbb{R}$, the sequence generated by the recurrence relation $$ a_{n+1} = |a_n| - a_{n-1} $$ turns out to be periodic with period 9, i.e., $$ a_n = a_{n+9} = a_{n+18} = a_{n+27} = \cdots $$ This is an interesting and unexpected fact, especially when you consider that to directly prove the periodicity (by writing down expressions for $a_2, \dots, a_9$ in terms of $a_0, a_1$), you would have to prove the following monstrous identity: $$ a_0 = -\left| \left| a_1\right| -a_0\right| -\left| -\left| \left| \left| a_1\right| -a_0\right| -a_1\right| +\left| a_1\right| +\left| -\left| \left| a_1\right| -a_0\right| +\left| \left| \left| \left| a_1\right| -a_0\right| -a_1\right| -\left| a_1\right| +a_0\right| +a_1\right| -a_0\right| +\left| \left| \left| \left| a_1\right| -a_0\right| -a_1\right| -\left| a_1\right| +a_0\right| +\left| \left| \left| \left| a_1\right| -a_0\right| -a_1\right| +\left| \left| \left| a_1\right| -a_0\right| +\left| -\left| \left| \left| a_1\right| -a_0\right| -a_1\right| +\left| a_1\right| +\left| -\left| \left| a_1\right| -a_0\right| +\left| \left| \left| \left| a_1\right| -a_0\right| -a_1\right| -\left| a_1\right| +a_0\right| +a_1\right| -a_0\right| -\left| \left| \left| \left| a_1\right| -a_0\right| -a_1\right| -\left| a_1\right| +a_0\right| -a_1\right| -\left| a_1\right| -\left| -\left| \left| a_1\right| -a_0\right| +\left| \left| \left| \left| a_1\right| -a_0\right| -a_1\right| -\left| a_1\right| +a_0\right| +a_1\right| +a_0\right| +a_1 $$ Of course, a straightforward "brute-force" approach this problem would be to consider sequentially the cases $a_1 > a_0 > 0$, $a_0 > 0 > a_1$, etc. and show that the RHS whittles down to the LHS in each case. But due to the simplicity of the original recurrence relation, I wonder if there isn't a more elegant way (hopefully involving less casework) to see that this recurrence must be 9-periodic.

Answer 1

Let me begin with a couple of remarks.

The sequence $(a_n)$ being periodic with period $9$ means that $a_{n+9}=a_n$ for all integers $n\geq 0$. The condition $a_9=a_0$ is not sufficient for $(a_n)$ to have period $9$, but if also $a_{10}=a_1$, then the recurrence, which computes a term from the preceding two terms, does start repeating the first nine values $a_0$, $a_1$, $\ldots$, $a_8$ over an over again.

Note that the recurrence relation also works backwards: $a_{n-1}=\left|a_n\right|-a_{n+1}$, so that for a given terms $a_0$ and $a_1$ we can calculate, recursively, the terms $a_n$ for all integers $n$. This observation provides another sufficient test of periodicity, namely $a_{-9}=a_0$ and $a_{-8}=a_1$, and on top of that (almost) halves the number of cases that must be considered, since by going backwards the roles of the initial terms $a_0$ and $a_1$ get interchanged. So, for example, after considering the case $0\leq a_0\leq a_1\leq 2a_0$ there is no need to consider the mirrored case $0\leq a_1\leq a_0\leq 2a_1$.

The cases themselves are not quite what you imagined; you did not actually work them through, or did you?

It suffices to consider five cases. Here they are, together with the terms $a_2$, $a_3$, $\ldots$, $a_8$, $a_9$, $a_{10}$ they produce:

Case $a_0,\,a_1\leq 0\,$: $-a_0\!-\!a_1$, $\,-a_0\!-\!2a_1$, $\,-a_1$, $\,a_0\!+\!a_1$, $\,-a_0$, $\,-2a_0\!-\!a_1$, $\,-a_0\!-\!a_1$, $\,a_0$, $\,a_1$.

Case $0\leq a_0\leq a_1\leq 2a_0\,$: $-a_0\!+\!a_1$, $\,-a_0$, $\,2a_0\!-\!a_1$, $\,3a_0\!-\!a_1$, $\,a_0$, $\,-2a_0\!+\!a_1$, $\,a_0\!-\!a_1$, $\,a_0$, $\,a_1$.

Case $0\leq 2a_0\leq a_1\,$: $-a_0\!+\!a_1$, $\,-a_0$, $\,2a_0\!-\!a_1$, $\,-a_0\!+\!a_1$, $\,-3a_0\!+\!2a_1$, $\,-2a_0\!+\!a_1$, $\,a_0\!-\!a_1$, $\,a_0$, $\,a_1$.

Case $a_0\leq0\leq a_1$, $a_0\!+\!a_1\geq 0\,$: $\,-a_0\!+\!a_1$, $\,-a_0$, $\,-a_1$, $\,a_0\!+\!a_1$, $\,a_0\!+\!2a_1$, $\,a_1$, $\,-a_0\!-\!a_1$, $\,a_0$, $\,a_1$.

Case $a_0\leq0\leq a_1$, $a_0\!+\!a_1\leq 0\,$: $\,-a_0\!+\!a_1$, $\,-a_0$, $\,-a_1$, $\,a_0\!+\!a_1$, $\,-a_0$, $\,-2a_0\!-\!a_1$, $\,-a_0\!-\!a_1$, $\,a_0$, $\,a_1$.

There are four other cases which we do not need to consider since they are mirror-symmetric to the cases two to five above.

How many cases are there? Five plus four. That's nine!

Let us enumerate the nine cases.

$(1)\,$ $\,x\leq 0\,$ and $\,y\leq 0\,$.

$(2)\,$ $\,0\leq x\leq y\leq 2x\,$.

$(3)\,$ $\,0\leq y\leq x\leq 2y\,$.

$(4)\,$ $\,0\leq 2x\leq y\,$.

$(5)\,$ $\,0\leq 2y\leq x\,$.

$(6)\,$ $\,x\leq 0\leq y\,$ and $\,x+y\geq 0\,$.

$(7)\,$ $\,y\leq 0\leq x\,$ and $\,x+y\geq 0\,$.

$(8)\,$ $\,x\leq 0\leq y\,$ and $\,x+y\leq 0\,$.

$(9)\,$ $\,y\leq 0\leq x\,$ and $\,x+y\leq 0\,$.

The cases are not mutually exclusive, but this does not affect the following result (prove it):

The mapping $(x,y)\to(y,\,\left|y\right|\!-\!x)$ maps a part of the $xy$-plane that corresponds to one of the cases $(1)$--$(9)$ into a part that corresponds to some other case, in the following cyclic order: $(1)\to(6)\to(2)\to(5)\to(9)\to(8)\to(4)\to(3)\to(7)\to(1)$.

We still have to prove that starting at any point, then applying the map nine times in a row, we will arrive back at precisely that point, and not only at some point of the part of the plane, corresponding to one of the cases, which contains the starting point. But now it suffices to consider only one case to which the starting point belongs: we choose a point that satisfies the condition of the case $(1)$, say, and then chase it all the way round, finding that we end at the chosen point.

Is this elegant enough?

[Added after the two comments about (non)elegance.]

I claim that we must know, in some way, the cases $(1)$--$(9)$ if we want to have a full an clear understanding of the $9$-periodic behavior of the sequence $(a_n)\,$: the nine cases are at the heart of the $9$-periodicity, they comprise its structure.

Denote by $T$ the mapping $\mathbb{R}^2\to\mathbb{R}^2$ that we have introduced above: $T(x,y) = (y,\,\left|y\right|\!-\!x)$. Then $T(a_{n-1},a_n)=(a_n,a_{n+1})$, which is precisely the reason why we introduced the transformation $T$. The fact that the sequence $(a_n)$ can be recurrently produced backwards means that the transformation $T$ is invertible; and indeed, $T^{-1}(x,y) = (\left|x\right|\!-\!y,\,x)$.

The part of the plane $\mathbb{R}^2$ corresponding to the case $(1)$ is the lower-left quadrant (the third quadrant), denote it by $Q$. Now look at the parts $T^k Q$, $0\leq k\leq 8\,$:

(The enumeration is by $k$ in $T^k Q$, not by the ad hoc case number. You may enjoy identifying the cases correponding to the $T^k Q$.)$\,$ The transformation $T$ appears as a highly uneven piecewise-linear attempt at realizing the idea "rotate clockwise by two ninths of the full turn". And with the figure in front of our noses we clearly see that $T^9$ is the identity transformation of the plane $\mathbb{R}^2$, which expresses in one breath the $9$-periodicity of all possible sequences $(a_n)$ generated by the given recurrence relation.

[Added some days later.]

It would be an extremely dull problem that could not inspire more problems. The recurrence given in the present question is not of the dull kind, it has an interesting cousin: \begin{equation*} a_{n+1} \,=\, \mathrm{sgn}(a_n) - a_{n-1}~, \qquad n\in\mathbb{Z}\,. \end{equation*} (The $\mathrm{sgn}(x)$ is the sign of a real number $x$: it is $1$ if $x>0$, it is $0$ if $x=0$, and it is $-1$ if $x<0$.) Like the original recurrence, this recurrence works also backwards: $a_{n-1}=\mathrm{sgn}(a_n)-a_{n+1}$. And like the original recurrence, each and every sequence $(a_n)$ it produces is periodic; the difference is that there is no common period, because there exist sequences that have arbitrarily large periods. So solving this recurrence offers much more fun. Another difference is that this time we do have a simple explanation of periodicity. Here's a hint. Define the transformation $U\colon\mathbb{R}^2\to\mathbb{R}^2$ by $U(x,y):=(y,\,\mathrm{sgn}(y)\!-\!x)$. Then for every integer $m\geq 1$ the transformation $U$ induces a bijection $U_m\colon S_m\to S_m$, where $S_m$ is the (closed) set The bijection $U_m$ is not continuous, it has a discontinuity along the line segment $L_m$ with endpoints $(-m,0)$ and $(m,0)$. However, the restrictions of $U_m$ to the line segment $L_m$ as well as to each of the two connected components of $S_m\setminus L_m$ are isometries. The bijection $U_m$ induces permutations of $2$-cells in $S_m$ (the open unit squares), of $1$-cells (the open unit line segments, the sides of the squares), and of $0$-cells (the points, the vertices of the squares); this implies finite periods. You may enjoy determining the periods of sequences $(a_n)$ generated by particular points $(a_0,a_1)\in\mathbb{R}^2$.