Sequence $a_n = a_{n - 1} + a_{\lfloor n/2 \rfloor}$

Given a sequence with $a_1 = 1$. And $a_n = a_{n - 1} + a_{\lfloor n/2 \rfloor}$ for $n \geq 2$, prove that $a_n$ is not divisible by 4 for any $n \in \mathbb{N}$.

Don't have any conjectures.

A few hints

Notice that $a_{2n+1}=a_{2n-1}+2a_n$. Since $a_1$ is odd, all $a_n$ are odd for odd $n$.

Then $a_{4n+2}=a_{4n+1}+a_{2n+1}$ even.

And $$a_{4n+2}=a_{4n+1}+a_{2n+1}=a_{4n-1}+2a_{2n}+a_{2n-1}+2a_n=a_{4n-2}+a_{2n-1}+3a_{2n-1}+4a_n=a_{4n-2}+4a_{2n-1}+4a_n$$ which shows by recurrence that $a_{4n+2}$ is not divisible by 4.

$a_{4n+4}=a_{4n+3}+a_{2n+2}$. In the case where $n$ is even, this is the sum of an even and an odd term. If $n$ is odd, $$a_{4n+4}=a_{4n+3}+a_{2n+2}=a_{4n+2}+a_{2n+1}+a_{2n+1}+a_{n+1}=a_{4n+2}+2a_{2n-1}+4a_n+a_{n+1}=2+2+a_{n+1} \ (\textrm{mod} \ 4) = a_{n+1}\ (\textrm{mod} \ 4)$$ Again by recurrence and contradiction (saying that $a_{4n+4}$ is the smallest element in the list to be divisible by 4) we show that $a_{4n+4}$ is not divisible by 4.

Normally this covers all the cases.