17

Prove that any sequence of real numbers satisfying $a_{n+1}=|a_n|-a_{n-1}$ is periodic.

Although it looks simple, I can't prove this statement...

I tried rewriting the first few terms of the sequence, but nothing interesting showed up...

I'd be mostly interested in hints for this one.

Gabriel Romon
  • 35,428
  • 5
  • 65
  • 157
  • From experimentation, it appears to have period $9$. This shouldn't be too hard to prove. – JimmyK4542 Aug 08 '14 at 06:38
  • @JimmyK4542 Did you succeed ? I can't find any trick to prove, without tedious case-checking, that it must have period $9$... – Gabriel Romon Aug 08 '14 at 06:45
  • I didn't really try, other than to write a computer program to check all combinations of $a_1,a_2 \in \overline{-100,100}$. Of course "This shouldn't be too hard to prove" doesn't imply that it won't be tedious. There might still be an elegant solution. – JimmyK4542 Aug 08 '14 at 06:47

2 Answers2

7

You can handle the problem this way. Assume $a_0=a$ and $a_1=b$.

The behaviour of the sequence always depends on the belonging of $(a,b)$ to one of the nine cones depicted below. By assuming, for example, that we starts with $(a,b)$ in the first cone ($a\geq 0,a\leq b\leq 2a$), the sequence is: $$ a,b,b-a,-a,2a-b,3a-b,a,b-2a,a-b,a,b,b-a,\ldots\tag{2}$$ and the period is $9$. By hand, we just have to check that this happens for any possible starting cone. Or be more clever. This is how the regions of the $(a,b)$-plane are mapped one into another:

Mapping of the $ab$-plane

Starting in any point, we come back to that point in $9$ steps. To put in elegant terms, the map $$\phi:(a,b)\to(b,|b|-a)$$ sends the $n$-th cone depicted in the $n+1$-th (the $9$th in the first one) with a bijection. Since the orbit of a point in the first cone is closed, the orbit of any point is closed, and its cardinality is nine.

Jack D'Aurizio
  • 353,855
  • so what happens in the $(>,<,<)$ case ? – mercio Aug 08 '14 at 07:39
  • In that case we have that $2$ is mapped into $3$, $3$ is mapped into $4$ and so on. We have a sequence that starts like $b,b-a$ in $(2)$. – Jack D'Aurizio Aug 08 '14 at 08:04
  • @JackD'Aurizio Nitpicking, but how do you know that the $(>,<,<)$ case starts in 2 ? It could start in 6, right ? – Gabriel Romon Aug 08 '14 at 08:10
  • No because the $(>,<,<)$ case is not represented on this diagram (btw you should mention me since I worked out those equations). Out of your "$8$ cases" there is only one that is relevant. I explained the proper method to get the relevant other cases while you just randomly assumed that the behaviour of the sequence depended on the signs of $3$ expressions. – mercio Aug 08 '14 at 08:12
  • @mercio: I fixed my argument. – Jack D'Aurizio Aug 08 '14 at 08:15
3

Once you guess that if $2a \ge b \ge a$, the sequence is $a,b,b-a,-a,2a-b,3a-b,a,b-2a,a-b,\ldots$ and that this sequence should cover all the possible cases,

you can translate the condition $2a \ge b \ge a $ to the other eight pairs of numbers and you should obtain a covering of the plane

For example if you do one step and let $a' = b, b' = b-a$, the condition becomes $2a'-2b' \ge a' \ge a'-b'$, so that $a' \ge 2b' \ge 0$. So this gives you a new region of the plane where you know that the sequence will be $9$-periodic because it is a shift of the original example.

For completeness' sake, here are the $9$ regions, in order :

$2a \ge b \ge a \\ a \ge 2b \ge 0 \\ a \ge 0 \ge a+b\\ b \ge 0 \ge a+b \\ b \ge 2a \ge 0 \\ 2b \ge a \ge b \\ a+b \ge 0 \ge b \\ 0 \ge a,b \\ a+b \ge 0 \ge a $

Those do form a covering of the plane so the template we used at the beginning covers all possible sequences.

mercio
  • 50,180