Irish Mathematical Olympiad

Assume that the sequence is not constant. Define a function $D: \mathbb{Z} \to [0, \infty)$ by the equation
$$D(n) = |a_{n+1} - a_n| + |a_{n+2} - a_{n+1}| + |a_{n+2} - a_n|,$$
or equivalently,
$$D(n) = 2(x_n - y_n), \quad (3)$$
where $x_n$ and $y_n$ are the largest and the smallest, respectively, of the three numbers $a_n, a_{n+1}, a_{n+2}$.
Note that if $D(n) = 0$ for any one value of $n$, then the original sequence would be constant. Thus by our assumption, we must have $D(n) > 0$ for all $n$. It is also trivial that $(a_n)$ is unbounded if the function $D$ is unbounded. We define $[x, y]$ to be the closed interval of values between the numbers $x$ and $y$. Unlike the usual meaning, we do not insist that $x \le y$, so $[x, y] = [y, x]$ is always an interval of length $|y - x|$.

Claim 1: $D$ is monotonically decreasing.
By translation invariance of the indices, it suffices to show that $D(0) \ge D(1)$. Bearing in mind that $a_3$ is an arithmetic average of $a_1, a_2$, and $a_0$, we see that if $a_0 \in [a_1, a_2]$, then $a_3 \in [a_1, a_2]$. Alternatively, if $a_0 \notin [a_1, a_2]$, then either $a_3 \in [a_1, a_2]$ or both $a_0$ and $a_3$ are on the same side of $[a_1, a_2]$, with $a_3$ being strictly closer than $a_0$ to $[a_1, a_2]$.
By the above considerations and (3), we deduce the following. If $a_0 \in [a_1, a_2]$, then $D(1) = D(0) = 2|a_2 - a_1|$. If instead $a_0 \notin [a_1, a_2]$, then either $a_3 \in [a_1, a_2]$, in which case $D(0) - D(1) = 2 \text{dist}(a_0, [a_1, a_2]) > 0$, or $a_3 \notin [a_1, a_2]$, in which case $D(0) - D(1) = 2|a_0 - a_3| > 0$. This shows that $D(0) \ge D(1)$ with equality iff $a_0 \in [a_1, a_2]$.

Claim 2: We cannot have $a_n \in [a_{n+1}, a_{n+2}]$ for two consecutive values of $n$.
As in Claim 1, we reduce to the statement that if $a_0 \in [a_1, a_2]$, then $a_1 \notin [a_2, a_3]$. Suppose $a_0 \in [a_1, a_2]$. As noted above, we then have $a_3 \in [a_1, a_2]$, which implies that $a_1 \notin [a_2, a_3]$ unless $a_1 = a_3$. But if $a_1 = a_3$, then our assumption that $a_0 \in [a_1, a_2]$ forces $a_0 = a_1 = a_2$, contradicting the initial assumption that $(a_n)$ is non-constant. Claim 2 now follows.
Claim 3: $D(n+3) < (2/3)D(n)$, $n \in \mathbb{N}$.
In view of Claims 1 and 2, it suffices to show that $D(n+2) < 2D(n)/3$ whenever $a_n \notin [a_{n+1}, a_{n+2}]$. As usual, we may assume that $n=0$. The function $D$ is invariant under translations of the sequence, and under multiplication by $-1$. So we may assume that $a_0 = 0$, and that $a := a_1$ and $b := a_2$ are both positive. Since
$$a_3 = \frac{a+b}{3} \quad \text{and} \quad a_4 = \frac{4a+4b}{9},$$
it follows that
$$\begin{align} D(0) &= a + |b-a| + b, \notag \ D(1) &= |b-a| + \frac{|a-2b|}{3} + \frac{|b-2a|}{3}, \tag{4} \ D(2) &= \frac{|a-2b|}{3} + \frac{|a+b|}{9} + \frac{|4a-5b|}{9}. \notag \end{align}$$
If $b \ge a$, then by (4), we have $D(0) = 2b$ and
$$D(2) = \frac{2b-a}{3} + \frac{a+b}{9} + \frac{5b-4a}{9} = \frac{12b-6a}{9} < \frac{4b}{3},$$
and so $D(2) < 2D(0)/3$, as required.
If instead $a/2 \le b < a$, then $D(0) = 2a$ and
$$D(1) = (a-b) + \frac{2b-a}{3} + \frac{2a-b}{3} = \frac{4a-2b}{3} < \frac{4a}{3}.$$
By Claim 1, we conclude that $D(2) \le D(1) < 2D(0)/3$, as required.
Finally, if $b < a/2$, then $D(0) = 2a$ and
$$D(2) = \frac{a-2b}{3} + \frac{a+b}{9} + \frac{4a-5b}{9} = \frac{8a-10b}{9} < \frac{8a}{9},$$
and so $D(2) < 4D(0)/9 \le 2D(0)/3$, as required. We have proved Claim 3.
With Claim 3 in hand, the unboundedness of $D(n)$ for negative $n$ follows easily.

Let $b_n = a_{-n}$, so we have $b_{n+3} = -b_{n+2} - b_{n+1} + 3b_n$ for all $n \in \mathbb{Z}$, and in particular for $n \ge 0$. The unique solution is $a_n = \beta r^n + \gamma s^n + \delta t^n$ for $n \ge 0$, where $r = 1$ and $s = \bar{t} = -1 + i\sqrt{2}$ are the three roots of the equation $x^3 + x^2 + x - 3 = 0$, and $\beta, \gamma, \delta \in \mathbb{C}$ depend on $b_0, b_1$, and $b_2$. Since every $a_n$ is real, $\beta$ is real and $\delta = \bar{\gamma}$. Thus $b_n = \beta + 2 \operatorname{Re}(\gamma s^n)$, $n \ge 0$. We assume that $(a_n)$ is non-constant, and so $\gamma \ne 0$.
Let $\arg : \mathbb{C} \setminus \{0\} \to (-\pi, \pi]$ be the argument function. Call $n \in \mathbb{Z}$ good if $|\arg(\gamma s^n)| < 3\pi/8$. Writing $c := \cos(3\pi/8) > 0$, we have $\operatorname{Re}(\gamma s^n) > c|\gamma| \cdot |s|^n$ whenever $n$ is good.
Now $\arg(s) = \pi - \tan^{-1} \sqrt{2}$, so
$$\arg(s) \in (\pi - \tan^{-1}\sqrt{3}, \pi - \tan^{-1}1) = (2\pi/3, 3\pi/4).$$
Thus the number $\gamma s^n / |\gamma s^n|$ "hops more than a full circuit around the unit circle" as $n$ ranges over a set of the form
$$S(n_0) := \{n_0, n_0 + 1, n_0 + 2, n_0 + 3\}, \quad n_0 \in \mathbb{Z},$$
and every $S(n_0)$ contains a good number $n$ (because $0 < \arg(s) < 2(3\pi/8)$). We can pick arbitrarily large good numbers $n \in \mathbb{N}$, and for each good $n$ we have $b_n > \beta + 2c|\gamma| \cdot |s|^n$. But if $(a_n)_{n=-\infty}^{\infty}$ were bounded, and hence $(b_n)_{n=0}^{\infty}$ bounded, then $|s|^n$ would be bounded for all $n \in \mathbb{N}$. This is impossible, since $|s| > 1$ and so if $|s|^n \le K$, then $n \log|s| \le \log K$, and $n \le \log K / \log|s|$ (where log indicates a logarithm to any preferred base).

This solution is similar to Solution 2, except that we take the more obvious approach of using the given recurrence relation directly. The solution is $a_n = \beta_0 r^n + \gamma_0 s^n + \delta_0 t^n$ for $n \ge 0$, where $r = 1$ and $s = \bar{t} = (-1 + i\sqrt{2})/3$ are the three roots of the equation $x^3 - (x^2+x+1)/3 = 0$, and $\beta_0, \gamma_0, \delta_0 \in \mathbb{C}$ depend on $a_0, a_1$, and $a_2$. Since every $a_n$ is real, $\beta_0$ is real and $\delta_0 = \bar{\gamma}_0$. Thus $a_n = \beta_0 + 2 \operatorname{Re}(\gamma_0 s^n)$ for $n \ge 0$; we call this Formula 1, and we need to show that it is also valid for $n < 0$. Assume that $(a_n)$ is non-constant, and so $\gamma_0 \ne 0$.
Suppose that $k \in \mathbb{N}$. The sequence $(b_n)_{n=0}^{\infty}$, where $b_n = a_{n-k}$, satisfies the same recurrence relation as $(a_n)$, so it can be written in the same form: $a_n = \beta_k + 2 \operatorname{Re}(\gamma_k s^{n+k})$ for $n \ge -k$; we call this Formula 2. To show that Formula 1 extends to $n = -k$, we need to show that $\beta_k = \beta_0$ and $\operatorname{Re}(\gamma_k s^{n+k}) = \operatorname{Re}(\gamma_0 s^n)$.
Let $d_k := \beta_k - \beta_0$. Comparing Formulae 1 and 2, we see that
$$2 \operatorname{Re}(\gamma_0 s^n) = 2 \operatorname{Re}(\gamma_k s^{n+k}) + d_k, \quad n \ge 0. \quad (5)$$
Taking half the difference of two such equations (for $n = 0$ and $n = m$), we get
$$\mathrm{Re}(\gamma_0(1 - s^m)) = \mathrm{Re}(\gamma_k s^k (1 - s^m))$$
and so
$$\mathrm{Re}((\gamma_0 - \gamma_k s^k)(1 - s^m)) = 0.$$
Now $\arg(1 - s^m)$ takes on different values for $m = 1, 2$, and these values do not differ by $\pi$, so it follows that $\gamma_0 = \gamma_k s^k$. Now (5) tells us that $d_k = 0$, i.e. $\beta_k = \beta_0$, and so Formula 1 is valid for $n = -k$.
Since $k \in \mathbb{N}$ is arbitrary, our solution for $n \ge 0$ is also valid for $n < 0$. The value of $s/|s|$ is the same as in Solution 2. Thus as before we see that there are infinitely many good values of $n < 0$ for which $\mathrm{Re}(\gamma s^n) > c|\gamma| \cdot |s|^n$. But $|s| < 1$, so as in Solution 2, boundedness is impossible.