11
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ For reference (it does not help answer the question, afaik): oeis.org/A033485 $\endgroup$ – Clement C. Jul 17 '17 at 17:55
  • $\begingroup$ Where is this question from? $\endgroup$ – Alex R. Jul 17 '17 at 18:20
  • $\begingroup$ @AlexR. Somebody told me a long ago about this problem. I generated the sequence and had a strong belief that this fact is true. $\endgroup$ – Symmetrical Jul 17 '17 at 18:23
  • $\begingroup$ 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. $\endgroup$ – Mnemonic Jul 17 '17 at 18:38
  • $\begingroup$ Actually, for odd $n$, the $a_n \bmod 4$ appear to follow the Thue-Morse sequence, but with 1 and 3. $\endgroup$ – Mnemonic Jul 17 '17 at 18:48
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.