$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$


1 Answer 1


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<k_2\le 12$, 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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .