Sequence is periodic $x_{n+2}=|x_{n+1}-x_{n-1}|$

Solution 1:

Each number in the sequence is an integer in the range $[0,\max(x_0,x_1,x_2)]$. As soon as you have three consecutive numbers appear in turn, that have previously appeared in that same order, then the sequence must repeat. Now apply the pigeonhole principle.

Solution 2:

ALSO POSTED ON A DIFFERENT QUESTION. The answers posted above don't complete the analysis to give the period, they only assert it exists - in fact the sequence need not be strictly periodic although the ultimate period is $7$ (I can't count and initially put $6$). The exception would be the null sequence (period $1$).

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$.

The constant $a$ is the highest common factor of the three initial values.

Solution 3:

Clearly \begin{align} &x_{n+2} =\lvert x_{n-1}-x_{n+1}\rvert\le \max\{x_{n-1}, x_{n+1}\}, \\ &x_{n+3} =\lvert x_n-x_{n+2}\rvert\le \max\{x_{n}, x_{n+2}\}, \\ \end{align} and hence $$ x_{n+3}\le \max\{x_{n+2},x_{n+3}\}\le\max\{x_{n-1},x_{n},x_{n+1},x_{n+2}\} $$ and recursively $$ x_n\le \max\{x_0,x_1,x_2,x_3\}=\max\{x_0,x_1,x_2\}=:N. $$ This means that $x_n\in\{0,1,\ldots,N\}$, for all $n\in\mathbb N$.

In particular, $$ (x_n,x_{n+1},x_{n+2})\in\{(i,j,k): 0\le i,j,k\le N\}=:S, $$ and since $S$ is finite, then there are $k,m\in\mathbb N$, such that $$ (x_\ell,x_{\ell+1},x_{\ell+2})=(x_{\ell+m},x_{\ell+m+1},x_{\ell+m+2}). $$ But, using the recursive definition, this implies that $x_{\ell+3}=x_{\ell+m+3}$, and inductively we obtain that $$ x_{\ell+j}=x_{\ell+m+j}, \quad \text{for all}\quad j\in\mathbb N. $$ Thus the sequence $\{x_n\}_{n\in\mathbb N}$ is periodic with period $m$.