# 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.

• For reference (it does not help answer the question, afaik): oeis.org/A033485 – Clement C. Jul 17 '17 at 17:55
• Where is this question from? – Alex R. Jul 17 '17 at 18:20
• @AlexR. Somebody told me a long ago about this problem. I generated the sequence and had a strong belief that this fact is true. – Symmetrical Jul 17 '17 at 18:23
• I don't have a proof, but if you write $n = x \cdot 2^y$, then it seems that for odd $y$, $a_n \equiv 2 \bmod 4$, and for even $y$, $a_n \equiv a_x \bmod 4$. Also, for odd $n$, $a_n$ is odd. – Mnemonic Jul 17 '17 at 18:38
• Actually, for odd $n$, the $a_n \bmod 4$ appear to follow the Thue-Morse sequence, but with 1 and 3. – Mnemonic Jul 17 '17 at 18:48

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.

• Last equality is mysterious.What is this [4]? – Takahiro Waki Jul 17 '17 at 19:51
• modulo 4. It is the notation I learnt, it does not seem to be universal... – fonfonx Jul 17 '17 at 19:54
• and I made a typo in last equality as well – fonfonx Jul 17 '17 at 19:56
• @TakahiroWaki in the last equality I used $a_{2n+1}=a_{2n-1}+2a_n$ to replace $a_{2n+1}$ – fonfonx Jul 17 '17 at 20:21