N3

Part of 2008 Balkan MO Shortlist

Problems(1)

Proving that terms of sequence are not divisible by 4

Source: Balkan MO ShortList 2008 N3

(\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