For all $n \in \mathbb{N}$ we define the function $\delta(n)=p$, where $p$ is sums of digits of $n^2$. For example if $n=17, \ n^2=289$, then $\delta(17)=2+8+9=19$.
Let $a_k$ is a monotonically increasing sequence of all positive integer numbers for which exist at least one $n(a_k) \in \mathbb{N}$ such that $\delta(n)=a_k$. And we define that $a_0=0$.
Find $a_{20122012}-?$.
This is a problem from my school math competition, and during this competition I found answer in the following way: simple calculations give us that $a_1=1, \ a_2=4, \ a_3=7, \ a_4=9, \ a_5=10, \ a_6=13, \ a_7=16, \ a_8=18, ...$. Then I notice that $a_4=a_0+9, a_5=a_1+9, a_6=a_2+9 ...$ so I guessed that for this sequence $a_{k+4}=a_{k}+9$. And this give us a very simple solution: if $k=4m+r$, where $r:\{0,1,2,3\}$ then $a_k=9m+a_r$. But I wasn't able to prove the main formula $a_{k+4}=a_{k}+9$ and lost some points because they said that it is not hard. But I still can't find the way how to prove it. So my
Question is: Is there exist a simple and nice way to prove that for this sequence $a_{k+4}=a_{k}+9$ - ? I guess that it is a well known problem. But is there some elementary solution?