Problem 1742

a. A sequence $(s_n)$ is subaveraging iff $s_{n+1} = 4s_n - s_{n-1}$ for all $n \in \mathbb{Z}$. This is equivalent to $s_{n-1} = 4s_n - s_{n+1}$ so that we can go backwards by the same recursion. The sequence $(s_n)$ is completely determined by $s_0$ and $s_1$.

For $s_0 = 0$ and $s_1 = 1$ we prove by induction that $0 \le s_n < s_{n+1}$ for all $n \ge 0$. The start of the induction is clear and for the step we have $s_{n+1} = 4s_n - s_{n-1} > 3s_n \ge s_n \ge 0$ for all $n \ge 1$.

Moreover, we obtain $s_{-1} = -1$ and so $s_{-n} = -s_n$ for all $n \ge 1$. This implies $s_{n-1} < s_n \le 0$ for all $n \le 0$ and we have shown that all entries of $(s_n)$ are distinct.

b. If $(s_k)$ is subaveraging, then the shifted sequence $(t_k)$ given by $t_k = s_{k+n}$ is subaveraging as well, because it satisfies the same recursion. The same is true for the reflected sequence $(r_k)$ given by $r_k = s_{-k}$, because the descending recursion $s_{n-1} = 4s_n - s_{n+1}$ translates into $r_{n+1} = 4r_n - r_{n-1}$.

Assume now that $(s_k)$ is a subaveraging sequence with $s_n = s_m$ and $n < m$. Consider the shifted sequence $t_k = s_{k+n}$ and the reflected and shifted sequence $r_k = s_{m-k}$. They satisfy $t_0 = r_0 = s_n$ and $t_{m-n} = r_{m-n} = s_n$. The difference $(d_k)$ of these subaveraging sequences, given by $d_k = t_k - r_k$, is subaveraging again (because the recursion is linear). We now have $d_0 = d_{m-n} = 0$. If $d_1 \ne 0$, we can divide each term of $(d_k)$ by $d_1$ and obtain another subaveraging sequence $q_k = d_k/d_1$ with $q_0 = 0$ and $q_1 = 1$. As we have seen in part (a), all entries of this sequence are distinct. This contradicts $m - n > 0$ and $q_{m-n} = 0$. Therefore, $d_1 = 0$ and so $d_k = 0$ for all $k \in \mathbb{Z}$. This implies that $t_k = r_k$, i.e. $s_{k+n} = s_{m-k}$ for all $k \in \mathbb{Z}$.