Team Selection Test for EGMO, 2024

Rearranging the condition, we obtain $(a_n - a_{n-1})^2 \ge 2a_{n-1}a_{n-2}$ and since the sequence is increasing we have $a_n \ge a_{n-1} + \sqrt{2a_{n-1}a_{n-2}}$. The inequality will be proved by induction over $n$.

For the base cases $n=2,3$ using the monotonicity we have $a_2 \ge a_1$ and $a_3 \ge a_2 + \sqrt{2a_2a_1} > a_2 + a_1$.

Assume that the assertion is true for $2, \dots, n-1$. There are two possible cases:

If $a_{n-1} < 2a_{n-2}$, then we have $a_n \ge a_{n-1} + \sqrt{2a_{n-1}a_{n-2}} \ge 2a_{n-1}$ and from the induction hypothesis we obtain $a_n \ge 2a_{n-1} \ge$
$$a_{n-1} + a_{n-2} + \dots + a_1.$$
If $a_{n-1} \ge 2a_{n-2}$, then we have $a_n \ge a_{n-1} + \sqrt{2a_{n-1}a_{n-2}} \ge a_{n-1} + 2a_{n-2}$ and from the induction hypothesis we obtain $a_n \ge a_{n-1} + 2a_{n-2} \ge a_{n-1} + a_{n-2} + \dots + a_1$.

We are done.

We will again use induction. Cases $n=2,3$ are covered in Solution 1. Assume that the assertion is true for $n=1,2,\dots,k$, we will prove that it is true for $n=k+1$. On the contrary, assume that $a_{k+1} < a_1 + \dots + a_k$. Then, we have $a_1 + \dots + a_{k-1} > a_{k+1} - a_k$. Since both sides are positive, we can take squares and use the problem condition to get
$$(a_1 + \dots + a_{k-1})^2 > (a_{k+1} - a_k)^2 \ge 2a_k a_{k-1}$$
From the inductive hypothesis we know that $a_k \ge a_1 + \dots + a_{k-1}$. Combining last two inequalities we get
$$a_1 + \dots + a_{k-1} > 2a_{k-1} \text{ or } a_1 + \dots + a_{k-2} > a_{k-1},$$
which contradicts to the inductive hypothesis. Thus,
$$a_{k+1} \ge a_1 + \dots + a_k.$$