62nd 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: $$\begin{gathered} 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{(ai−ai−1−1 terms)}}<(a_{i-1}+1)+(a_i-a_{i-1}-1)=a_i. \end{gathered}$$ 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,\dots ,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$.