Шелковый путь олимпиада по математике 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$.