Шелковый путь олимпиада по математике 2019 года | Казахстанские олимпиады

Последовательность $\{a_n\}$ определена следующим образом: $a_0=1$ и ${a_n} = \sum\limits_{k = 1}^{[\sqrt n ]} {{a_{n - {k^2}}}}$ для $n \ge 1.$ Докажите, что среди $a_1,a_2,\ldots,a_{10^6}$ есть хотя бы 500 четных чисел. (Здесь $[x]$ обозначает наибольшее целое, не превосходящее $x$.)