Below is a problem, from an old Silk Road olympiad.

Define an infinite sequence, $a(n)$, such that, $a(1)=a(2)=1$;
$$
a(n)=a(a(n-1))+a(n-a(n-1)),\forall n\geq 3.
$$
Show that, for every $n\geq 1$, $a(2n)\leq 2a(n)$.