# Sequence and Floor fucntion $a_n = a_{n-1} + a_{\lfloor \frac{n}{3} \rfloor}$

$$a_0=5, a_1 =2$$ $$a_n = a_{n-1} + a_{\lfloor \frac{n}{3} \rfloor}$$ Prove that there are infinitely many $$i \in \mathbb{N}$$ such that $$13 \mid a_i$$

I have no idea for this problem, please help me. You can see that $$i = 5, 10, 22, ...$$

$$a_2=7, a_3=9, a_4=11, a_5=13, a_6=20, a_7=27, a_8=34, a_9=43, a_{10}=52, ..., a_{22}=247$$

Assume the contrary, i.e., the set $$I=\{5,10,22,\ldots\}$$ of indices where $$a_n\equiv 0\pmod{13}$$ is finite (but non-empty!). Let $$N=\max I$$ (so certainly $$I\ge 22$$). Then $$a_{3N-1}\equiv a_{3N}\equiv a_{3N+1}\equiv a_{3N+2}\pmod {13}.$$ Next, the thirteen terms $$a_{9N-4},\ldots, a_{9N+7}$$ are in an arithmetic progression modulo $$13$$, i.e., $$a_{9N-4+k}\equiv a_{9N-4}+k\cdot a_{3N}\pmod {13}$$ for $$k=0,1,\ldots, 12$$. As $$a_{9N-4+k}\equiv 0$$ would contradict $$9N-4+k>N$$, we see from the pigeon-hole principle that two of these terms must be congruent, i.e., $$a_{9N-4}+k_1\cdot a_{3N}\equiv a_{9N-4}+k_2\cdot a_{3N}\pmod {13}$$ with $$0\le k_1, and from this $$(k_2-k_1)a_{3N}\equiv 0\pmod{13}.$$ As $$13$$ is prime, we must have $$k_2-k_1\equiv 0$$ or $$a_{3N}\equiv 0$$, both of which are absurd.
Apparently, the same argument works with any prime $$p$$ and sequence with recursion $$a_n=a_{n-1}+a_{\lfloor n/d\rfloor},$$ provided $$p\le d^2+d+1$$ and there exists at least on (small) $$a_n$$ that is a multiple of $$p$$.