Balkan Mathematical Olympiad Shortlist

First, for $k\in \mathbb{N}$, $k\ge 2$, we have $$a_{2k+1}+a_{2k-1}=2a_{2k}-a_k+a_{2k-1}=5a_{2k-1}-a_k\equiv -a_k(\mathrm{mod}5).(1)$$ We prove the assertion of the problem by induction on $k$, where $n=8k+3$. For the base case $k=1$, we compute $a_3=1$, $a_4=2$, $a_5=3$, $a_6=6$, $a_7=11$, $a_8=22$, $a_9=42$, $a_{10}=84$ and $a_{11}=165$. By repeatedly applying (1), we have $$\begin{array}{rl}{a}_{8(k+1)+3}-a_{8k+3}& =(a_{8k+11}+a_{8k+9})-(a_{8k+9}+a_{8k+7})\\ & +(a_{8k+7}+a_{8k+5})-(a_{8k+5}+a_{8k+3})\\ & \equiv -a_{4k+5}+a_{4k+4}-a_{4k+3}+a_{4k+2}\\ & =-a_{4k+5}+a_{4k+3}+2a_{4k+1}\\ & =-(a_{4k+5}+a_{4k+3})+2(a_{4k+3}+a_{4k+1})\\ & \equiv a_{2k+2}-2a_{2k+1}=0(\mathrm{mod}5).\end{array}$$ Therefore, if $a_{8k+3}$ is divisible by 5, so is $a_{8(k+1)+3}$. This completes the proof.