EGMO

Solution:

We claim that the sequence $b_{1}, b_{2}, b_{3}, \ldots$ defined by $b_{i} = 2i - 1$ has this property.
Let $d_{i} = a_{i} - b_{i} = a_{i} - 2i + 1$. The condition $a_{i} < a_{i + 1}$ now becomes $d_{i} + 2i - 1 < d_{i + 1} + 2i + 1$, which can be rewritten as $d_{i + 1} \geqslant d_{i} - 1$. Thus, if $d_{i + 1} < d_{i}$, then $d_{i + 1}$ must be equal to $d_{i} - 1$. This implies in particular that if $d_{i_{0}} \geqslant 0$ but $d_{i_{1}} \leqslant 0$ for some indices $i_{1} > i_{0}$, there must be some intermediate index $i_{0} \leqslant i \leqslant i_{1}$ with $d_{i} = 0$.

Because the average of the first $a_{n}$ terms of the sequence is equal to $a_{n}$, we know for all $n$ that
$$\sum_{i = 1}^{a_{n}} d_{i} = \sum_{i = 1}^{a_{n}} (a_{i} - 2i + 1) = \sum_{i = 1}^{a_{n}} a_{i} - \sum_{i = 1}^{a_{n}} (2i - 1) = a_{n}^{2} - a_{n}^{2} = 0.$$
Because the sequence $(a_{n})$ is increasing, this implies that the sequence $(d_{i})$ contains infinitely many non-negative $(d_{i} \geqslant 0)$ and infinitely many non-positive $(d_{i} \leqslant 0)$ terms. In particular, we can find arbitrarily large indices $i_{0} \leqslant i_{1}$ such that $d_{i_{0}} \geqslant 0$ and $d_{i_{1}} \leqslant 0$. By our earlier observation, it follows that there are infinitely many $i$ such that $d_{i} = 0$, as desired.

Solution:

We give an alternative proof that the sequence $b_{i} = 2i - 1$ works. This proof is by contradiction, so we assume that there are only finitely many $a_{i}$ such that $a_{i} = 2i - 1$.

Let $S(n) = \sum_{i = 1}^{n} a_{i}$. We have $S(a_{n}) = a_{n}^{2}$ and $S(a_{n + 1}) = a_{n + 1}^{2}$. If $a_{n + 1} = a_{n} + 1$, then it follows that
$$S(a_{n + 1}) - S(a_{n}) = a_{n + 1}^{2} - a_{n}^{2} = a_{n + 1}^{2} - (a_{n + 1} - 1)^{2} = 2a_{n + 1} - 1.$$
On the other hand, if $a_{n + 1} = a_{n} + 1$, then $S(a_{n + 1}) - S(a_{n})$ is $a_{a_{n + 1}}$, so it follows that $a_{a_{n + 1}} = 2a_{n + 1} - 1$. By assumption, this can only happen finitely many times, so for all sufficiently large $n$ we must have $a_{n + 1} \geqslant a_{n} + 2$.

For large enough $n$, we now know that $a_{n} > 2n - 1$ implies $a_{n + 1} > (2n - 1) + 2 = 2(n + 1) - 1$. This means that there are two cases possible:

(A) For all sufficiently large $n$ (say $n \geqslant N_{A}$) we have $a_{n} > 2n - 1$

(B) For all sufficiently large $n$ (say $n \geqslant N_{B}$) we have $a_{n} < 2n - 1$

In case (A), we know for $m > N_{A}$ that
$$S(m) = S(N_{A}) + \sum_{i = N_{A} + 1}^{m} a_{i} \geqslant S(N_{A}) + \sum_{i = N_{A} + 1}^{m} 2i = S(N_{A}) + m(m + 1) - N_{A}(N_{A} + 1)$$
$$\qquad = m^{2} + m + S(N_{A}) - N_{A}(N_{A} + 1).$$
For $m$ large enough (e.g. $m > N_{A}(N_{A} + 1)$), this expression is always larger than $m^{2}$, contradicting $S(a_{n}) = a_{n}^{2}$ for all $n$.

Similarly, in case (B), we similarly know for $m > N_{B}$ that
$$S(m) = S(N_{B}) + \sum_{i = N_{B} + 1}^{m} a_{i} \leqslant S(N_{B}) + \sum_{i = N_{B} + 1}^{m} 2(i - 1) = S(N_{B}) + m(m - 1) - N_{B}(N_{B} - 1)$$
$$\qquad = m^{2} - m + S(N_{B}) - N_{B}(N_{B} - 1).$$
For $m$ large enough (e.g. $m > S(N_{B})$), this expression is always smaller than $m^{2}$, again contradicting $S(a_{n}) = a_{n}^{2}$ for all $n$.

Solution:

We claim that the sequence $b_{1}, b_{2}, b_{3}, \ldots$ defined by $b_{i} = 2i - 1$ has this property.

Lemma. If there are no terms $a_{j}$ such that $a_{j} - a_{j - 1} = 1$, then $a_{j} = a_{j - 1} + 2$ for all $j$.

Proof. Let $c$ be such that $a_{d} = c$ for some $d$. Now
$$a_{1} + a_{2} + \dots + a_{c} = c^{2}.$$
Equality holds for $a_{i} = 2i - 1$ for $1 \leq i \leq c$, so if any difference between two consecutive terms is greater, the left-hand side of the equation is greater than $c^{2}$, a contradiction. $\square$

Lemma. If both $d$ and $d + 1$ are terms of the sequence, i.e. $a_{c} = d$ and $a_{c + 1} = d + 1$ for some $c$, then $a_{d + 1} = 2d + 1 = b_{d + 1}$.

Proof. We have $a_{1} + a_{2} + \dots + a_{d} = d^{2}$ and $a_{1} + a_{2} + \dots + a_{d + 1} = (d + 1)^{2}$. Hence $a_{d + 1} = (d + 1)^{2} - d^{2} = 2d + 1$. $\square$

From the observations above, we see that we are done if there are infinitely many gaps of size 1. The only remaining case is one with finitely many gaps of size 1. This will be the subject of the following lemma.

Lemma. If there are only finitely many indices $j$ such that $a_{j + 1} - a_{j} = 1$, then there is an index $n_{0}$ such that for all $k > n_{0}$, we have $a_{k} = 2k - 1$.

Proof. Let $r$ and $s$ be indices such that for all the $j$ satisfying $a_{j + 1} - a_{j} = 1$, we have $j < r$, $s$. Furthermore, assume $s > r$ and that there are $i_{1}$ and $i_{2}$ such that $a_{i_{1}} = r$ and $a_{i_{2}} = s$. The first goal is to show that $a_{s} \geq 2s - 1$. If $a_{r} \geq 2r - 1$, this is clearly the case. Assume now $a_{r} < 2r - 1$. Now $a_{r} \geq 2r - 1 - m$, where $m$ is the number of indices $j$ with $a_{j + 1} - a_{j} = 1$. Denote $a_{r + 1} = 2r + 1 - m + \theta_{1}$, $a_{r + 2} = 2r + 3 - m + \theta_{2}$, etc. Remember that $a_{r + j + 1} - a_{r + j} \geq 2$ always. Now $0 \leq \theta_{1} \leq \theta_{2} \leq \dots$. Furthermore, write $s = r + h$. Now
$$(r + h)^{2} - r^{2} = a_{r + 1} + a_{r + 2} + \dots + a_{r + h} = \sum_{j = 1}^{h} 2r - 1 + 2j - m + \theta_{j}.$$
From this we deduce
$$2r h + h^{2} = 2r h - h - m h + h(h + 1) + \sum_{j = 1}^{h} \theta_{j}.$$
So we obtain $\sum_{j = 1}^{h} \theta_{j} = m h$. Since the sequence $\theta_{j}$ is increasing, we have $\theta_{h} \geq m$. Hence, $a_{s} = a_{r + h} \geq 2r - 1 - m + 2h + m = 2r + 2h - 1 = 2s - 1$.

Now $a_{s}$ is exactly the desired shape. If for any $t > s$, we have $a_{t} - a_{t - 1} > 2$, then
$$a_{s} + a_{s + 1} + \dots + a_{t} > t^{2} - s^{2},$$
again a contradiction.

Solution:

Note that $a_{1} = 1$ because if it is not the case, then $a_{1}^{2} = a_{1} + \dots + a_{a_{1}} > a_{1} + a_{1} + \dots + a_{1} = a_{1}^{2}$.

Assume by contradiction that there are only finitely many indices $k$ such that $a_{k} = 2k - 1$. Set $i$ to be the largest integer such that $a_{i} = 2i - 1$ (which must exist as $a_{1} = 1$). Assume that there exists $j \geqslant i$ such that $a_{j + 1} - a_{j} = 1$. Then $2a_{j + 1} - 1 = a_{j + 1}^{2} - a_{j}^{2} = a_{a_{j + 1}}$ and since $a_{k} \geqslant k$ for all $k$, we have $a_{j + 1} \geqslant j + 1 > i$, which contradicts the definition of $i$. Thus for all $j \geqslant i$, we have $a_{j + 1} \geqslant a_{j} + 2$, which implies by induction that $a_{j} \geqslant 2j - 1$ for $j \geqslant i$, and even $a_{j} \geq 2j$ if $j > i$.

There are two ways to finish the solution from here.

## First way to finish the solution
For all $n$ such that $a_{n} \geqslant i$, we have
$$a_{n + 1}^{2} - a_{n}^{2} = a_{a_{n + 1}} + a_{a_{n + 1} - 1} + \dots + a_{a_{n + 1}} \geqslant 2a_{n + 1} + 2(a_{n + 1} - 1) + \dots + 2(a_{n} + 1)$$
$$\qquad = (a_{n + 1} - a_{n})(a_{n + 1} + a_{n} + 1)$$
$$\qquad > a_{n + 1}^{2} - a_{n}^{2}.$$
This gives a contradiction.

## Second way to finish the solution
For all $n$ such that $a_{n} \geqslant i$, we introduce $x_{n} = a_{n + 1} - a_{n}$. We have
$$x_{n}^{2} + 2x_{n} a_{n} = a_{n + 1}^{2} - a_{n}^{2} = a_{a_{n + 1}} + a_{a_{n + 1} - 1} + \dots + a_{a_{n} + 1} \geqslant \sum_{j = 1}^{x_{n}} (a_{a_{n}} + 2j) \geq x_{n} a_{a_{n}} + x_{n}(x_{n} + 1).$$
By simplifying, we get $a_{a_{n}} \leq 2a_{n} - 1$, which gives a contradiction.