Divisibility of sequence Let the sequence $x_n$ be defined by $x_1=1,\,x_{n+1}=x_n+x_{[(n+1)/2]},$ where $[x]$ is the integer part of a real number $x$. This is A033485. How to prove or disprove that 4 is not a divisor of any its term? The problem belongs to math folklore. As far as I know it, M. Kontsevich authors that. 
 A: For $n\in\Bbb Z^+$ let $u_n=x_n\bmod 4$, and let $\oplus$ denote addition modulo $4$. We have the recurrences
$$\left\{\begin{align*}
u_{2n}&=u_{2n-1}\oplus u_n\\
u_{2n+1}&=u_{2n}\oplus u_n\;,
\end{align*}\right.$$
and the first few values are $u_1=1,u_2=2,u_3=3$, and $u_4=1$. The desired result is an immediate corollary of the following proposition.

Proposition. For all $n\in\Bbb Z^+$, $u_{4n}=u_n$, $u_{4n+1},u_{4n+3}\in\{1,3\}$, and $u_{4n+2}=2$. 

The proof is by induction on $n$. For $n>1$ we have
$$\begin{align*}
u_{4n}&=u_{4n-1}\oplus\color{blue}{u_{2n}}\\
&=\color{blue}{u_{4n-1}}\oplus u_{2n-1}\oplus u_n\\
&=\color{blue}{u_{4n-2}}\oplus 2u_{2n-1}\oplus u_n\\
&=\color{blue}{u_{4n-3}}\oplus 3u_{2n-1}\oplus u_n\\
&=\color{blue}{u_{4n-4}}\oplus u_{2n-2}\oplus 3u_{2n-1}\oplus u_n\\
&=\color{blue}{u_{n-1}\oplus u_{2n-2}}\oplus 3u_{2n-1}\oplus u_n\\
&=\color{blue}{4u_{2n-1}}\oplus u_n\\
&=x_n\;,
\end{align*}$$
where on each line I’ve highlighted in blue the term(s) to be manipulated to get the next line.
Then we have
$$\begin{align*}
&u_{4n+1}=u_{4n}\oplus u_{2n}=u_n\oplus u_{2n}=u_{2n+1}\in\{1,3\}\;,\\
&u_{4n+2}=u_{4n+1}\oplus u_{2n+1}=u_{2n+1}\oplus u_{2n+1}=2\;,\text{ and}\\
&u_{4n+3}=u_{4n+2}\oplus u_{2n+1}=2\oplus u_{2n+1}\in\{1,3\}\;,
\end{align*}$$
and the induction goes through.
A: Prove by induction that modulo $4$,
$y_n = (x_n, (x_{2n-1}, x_{2n}, x_{2n+1}))$ is always one of the following quadruplets :
$(1,(1,2,3)) ;  (2,(1,3,1)) ; (2,(3,1,3)) ;  (3,(3,2,1))$
($x_n$ and $x_{2n-1}$ determine the other two values so this is also saying that $(x_n,x_{2n-1})$ can never be $(1,2),(1,3),(2,2),(3,1)$ or $(3,2)$)
We check that $y_1 = (1,(1,2,3))$.  
If $y_n = (1,(1,2,3))$ then since $1$ can only be followed by $2$ or $3$, either $x_{n+1} = 2$ and $y_{n+1} = (2,(3,1,3))$, either $x_{n+1} = 3$ and $y_{n+1} = (3,(3,2,1))$.
If $y_n = (3,(3,2,1))$ then since $3$ can only be followed by $1$ or $2$, either $x_{n+1} = 1$ and $y_{n+1} = (1,(1,2,3))$, either $x_{n+1} = 2$ and $y_{n+1} = (2,(1,3,1))$.
If $x_n = 2$ then $n = 2k$ and $y_k$ is $(1,(1,2,3))$ or $(3,(3,2,1))$.
In the first case we get $y_{n-1} = (1,(1,2,3)), y_n = (2,(3,1,3))$ and $y_{n+1} = (3,(3,2,1))$
In the other case we get $y_{n-1} = (3,(3,2,1)), y_n = (2,(1,3,1))$ and $y_{n+1} = (1,(1,2,3))$

Shape those quadruplet as a small triangle piece.
Here is the picture of the possible ways those pieces can interact : From the possible top and left pieces (determined by $x_n,x_{2n-1},x_{4n-3}$) we compute the other values and see that the next two pieces are still of the $4$ possible kind.

