Periodic sequence [duplicate]

This question already has an answer here:

$(x_n)_n$ is a sequence defined by the relation: $x_{n+2}=|x_{n+1}-x_{n-1}|$ for $n\geq1$ and $x_0,x_1,x_2$ are non-negative integers, not all three equal 0. I think this sequence is periodic, so here is my question: is it true and if yes which is the period? Thank you!

marked as duplicate by Gerry Myerson, Mark Bennet, user127.0.0.1, Yiorgos S. Smyrlis, TZakrevskiyFeb 22 '14 at 11:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

Yes the sequence is periodic.

The period depends on the $\max\{x_0,x_1,x_2\}$.

Note that the absolute value of the $x_r$ is at most the maximum of $x_{k-2}, x_{k-1}, x_k$ for any $k\lt r$ - we can't get a greater value than we've had already, so there is a point in the sequence where we hit the highest value.

Suppose $x_{n-1}$ is the highest possible value. We have $x_{n+2}=x_{n-1}$ only if $x_{n+1}=0$ and this is true only if $x_n=x_{n-2}$ so if the highest value $a$ is sustained we have $\dots x_{n-2}, x_{n-1}, x_n, x_{n+1}, x_{n+2} \dots = \dots b, a, b, 0, a \dots$ with $a\ge b$.

The sequence then continues $\dots b,a,b,0,a,a-b,a-b,b \dots$, and unless $b=a$ or $b=0$ the maximum value within the tail of the sequence has decreased (since any three consecutive terms define the rest of the sequence, and we could consider the tail of the sequence as starting with $a-b, a-b, b$). Since we can't have an infinite decreasing sequence of non-negative numbers we must reach the situation where $a=b$ when the sequence goes:

$$\dots a,a,a,0,a,0,0,a,a,a \dots$$

When $b=0$ we get the same sequence shifted $$\dots 0,a,0,0,a,a,a,0,a,0 \dots$$So the sequence starts off decreasing before becoming periodic. If it turns out that $a=0$ there is ultimate period $1$ (constant) otherwise ultimate period $7$.