Ukrainian National Mathematical Olympiad

Note that we can put $a_0 = 0$, then we would get $a_1 = 1$. First, let's prove the following lemma:

Lemma. For all $i \in \mathbb{N}$ the condition holds: $a_{i+1} - a_i \ge a_i - a_{i-1}$.

Proof:
$$x_1 + x_2 + \cdots + x_{2a_i - a_{i-1} - 1} = (x_1 + x_2 + \cdots + x_{a_i}) + (x_{a_i + 1} + x_{a_i + 2} + \cdots + x_{2a_i - a_{i-1} - 1}) < \\ < (a_{i-1} + 1) + (1 + 1 + \cdots + 1)_{\text{($a_i - a_{i-1} - 1$ terms)}} < (a_{i-1} + 1) + (a_i - a_{i-1} - 1) = a_i.$$
Thus, $a_{i+1}$ there must be at least $2a_i - a_{i-1}$.

Let's choose some positive integer $t$. First, write down the inequalities of the form $a_{i-k} - a_{i-k-1} \ge a_{i-k-1} - a_{i-k-2}$, $k = 0, \ldots, t-1$.
Add up all these inequalities: $a_i - a_{i-t} \ge a_{i-1} - a_{i-t-1}$ and then we have that
$$a_i - a_{i-t} \ge a_{i-1} - a_{i-t-1} \ge a_{i-2} - a_{i-t-2} \ge \cdots \ge a_t - a_0.$$
Now we just put $i \to i+j$, $t \to j$ and get the desired inequality from the problem: $a_{i+j} \ge a_i + a_j$.