IV математическая олимпиада «Шелковый путь», 2005 год

Пусть бесконечная последовательность $a(1), a(2), \ldots$ определена следующим образом: $a(1) = a(2) = 1$ и $$a(n) = a(a(n - 1)) + a(n - a(n - 1)) \text{ при } n \ge 3.$$ Докажите, что $a(2n) \le 2a(n)$ при всех $n \ge 1$.