BMO 2008 SL N3 wrote: The sequence $(\chi_n) _{n=1}^{\infty}$ is defined as follows \begin{align*} \chi_{n+1}=\chi_n + \chi _{\lceil \frac{n}{2} \rceil} ~, \chi_1 =1 \end{align*}Prove that none of the terms of this sequence are divisible by $4$ For convenience let us replace $(\chi_n)$ with $(a_n)$. The given condition rewrites as $$a_{2n+1}=a_{2n}+a_n$$and $$a_{2n+2}=a_{2n+1}+a_{n+1}$$ We proceed with some Claims. Claim 1: $a_{2n+1}$ is odd, for all $n \geq 0$. Proof: Note that $$a_{2n+1}+a_{2n-1}=a_{2n}+a_n+a_{2n-1}=a_{2n}+a_{2n}=2a_{2n} \equiv 0 \pmod 2$$hence all terms of the form $a_{2n+1}$ are either odd or even. Since $a_1=1$, we infer that all $a_{2n+1}$ are odd $\blacksquare$ Claim 2: $a_{4n+2}-a_{4n-2}=4a_{2n}$ for all $n \geq 1$. Proof: We have $$a_{4n+2}-a_{4n-2}=a_{4n+1}+a_{2n+1}-a_{4n-2}=a_{4n}+a_{2n}+a_{2n+1}-a_{4n-2}=a_{4n-1}-a_{4n-2}+2a_{2n}+a_{2n+1}=a_{2n-1}+a_{2n+1}+2a_{2n}=4a_{2n}$$hence we are done $\blacksquare$ Claim 3: $a_{4n+2} \equiv 2 \pmod 4$ for all $n \geq 0$. Proof: From Claim 2 all terms of the form $a_{4n+2}$ are equal $\pmod 4$, and since $a_2=2$ we obtain the desired $\blacksquare$ Claim 4: $a_{4n+4} \equiv a_{n+1} \pmod 4$ for all $n \geq 0$ Proof: We have $$a_{4n+4}=a_{4n+3}+a_{2n+2}=a_{4n+2}+a_{2n+2}+a_{2n+1}=a_{4n+2}+2a_{2n+1}+a_{n+1} \equiv 2+2+a_{n+1} \equiv a_{n+1} \pmod 4,$$hence we are done (we used the results of Claims 1 and 3) $\blacksquare$ To the problem, from Claims 1 and 3 we have that $4 \nmid a_{2n+1}$ and $4 \nmid a_{4n+2}$ for all $n$ so the only case left to examine is whether $4 \mid a_{4m}$ for some $m$. If this was the case, then from Claim 4 $a_{4m} \equiv a_m \pmod 4$, hence $4 \mid a_m$. If $m$ is odd or $\equiv 2 \pmod 4$ we have a contradiction due to Claims 1 and 3. Hence $4 \mid m$. So we obtain $a_m \equiv a_{\frac{m}{4}} \pmod 4$, so $4 \mid a_{\frac{m}{4}}$. That is, $4 \mid \frac{m}{4}$. Obviously, this cannot go on indefinitely, so we obtain a clear contradiction. Hence we are done.

Also Bulgaria RMM TST 2019