Can someone help with this question:
Let $a_0,a_1,a_2,...$ be a sequence of real numbers satisfying $a_0=1$ and $a_n=a_\left\lfloor{\frac{7n}{9}}\right \rfloor + a_\left\lfloor{\frac{n}{9}}\right\rfloor$ for $n=1,2,...$
Prove that there exists a positive integer $k$ such that $a_k < \frac{k}{2001!}$.
I tried using proof by contradiction by assuming $a_n<\frac{n}{2001!}$ for all $n\geq0$, but I could not arrive at a contradiction. I also examined the function's rate of change and it seems like this function has a "lower complexity" than a linear function i.e. the function has a smaller rate of change than a linear function $a_n=kn$ for some positive value $k$, but I could not find a proof for this.
I also tried finding the general term, but I could not figure out how to simplify the recursive formula.