$x_1 = 2$, $x_{n + 1} = {{x_n(x_n + 1)}\over2}$, what can we say about $x_n \text{ mod }2$? Let$$x_1 = 2, \quad x_{n + 1} = {{x_n(x_n + 1)}\over2}.$$What can we say about the behavior of $x_n \text{ mod }2$? Is there an exact formula for $x_n \text{ mod }2$?
 A: It is not complete answer, but too long for comment.
First of all, for the sake of convenience let us define $y_n=x_{n+1}$, then, according to the algorithm in this paper recurrence $y_{n+1}=\frac{1}{2}y_n^2+\frac{1}{2}y_n$, $y_0=2$, has following solution:
$$
y_n=\left\langle\textbf{e}\left|T_{jk}^n\right|\textbf{y}\right\rangle
$$
Where $\langle\textbf{e}|=\{\delta_{j1}\}^\infty_{j=0}-$ row-vector, $\delta_{jk}-$ Kronecker symbol; $|\textbf{y}\rangle=\{2^j\}^\infty_{j=0}-$ column-vector; and $T-$ matrix, which elements defined as $T_{jk}=\left(
    \begin{array}{c}
      j \\
      k-j
    \end{array}
  \right)2^{-j}$.
Components of $T_{jk}^n$ can be represented as: $$(T^n)_{i_{0}i_{n}}=\sum^\infty_{i_1=0}\sum^\infty_{i_2=0}...\sum^\infty_{i_{n-1}=0}T_{i_{0}i_{1}}T_{i_{1}i_{2}}...T_{i_{n-1}i_{n}}$$
However, we know that $\langle \textbf{e}|T^n_{jk}=\langle \textbf{e}|(T^n)_{jk}=T^n_{1k}$, hence we do not need all components, but only:
$$
(T^n)_{1i_n}=\sum^\infty_{i_1=0}\sum^\infty_{i_2=0}...\sum^\infty_{i_{n-1}=0}T_{1i_{1}}T_{i_{1}i_{2}}...T_{i_{n-1}i_{n}}
$$
Which leads to 
$$
y_n=\sum^\infty_{i_n=0}\sum^\infty_{i_1=0}\sum^\infty_{i_2=0}...\sum^\infty_{i_{n-1}=0}T_{1i_{1}}T_{i_{1}i_{2}}...T_{i_{n-1}i_{n}}2^{i_n}
$$
And it's where hard part starts, hypergeometric functions popping up and so on.
Comparance to the expansion from initial reccurance. 
For example, consider the case of $x_3=y_2$:
$$
y_2=\sum^\infty_{i_2=0}\sum^\infty_{i_1=0}\sum^\infty_{i_2=0}\left(
    \begin{array}{c}
      1 \\
      i_1-1
    \end{array}
  \right)2^{-1}\left(
    \begin{array}{c}
      i_1 \\
      i_2-i_1
    \end{array}
  \right)2^{-i_1}2^{i_2}\to\\
y_2=\sum^\infty_{i_2=0}\left[\left(
    \begin{array}{c}
      1 \\
      i_2-1
    \end{array}
  \right)2^{-2}+\left(
    \begin{array}{c}
      2 \\
      i_2-2
    \end{array}
  \right)2^{-3}\right]2^{i_2}\to\\
y_2=\left[0\right]2^0+\left[2^{-2}\right]2^1+\left[2^{-2}+2^{-3}\right]2^2+\left[2*2^{-3}\right]2^3+\left[2^{-3}\right]2^4\to\\
y_2=0+2^{-1}+[1+2^{-1}]+2+2=6
$$
At the same time:
$$
y_2=\frac{1}{2}y_1^2+\frac{1}{2}y_1\to\\
y_2=\frac{1}{2^3}\left[y_0^4+2y_0^3+y_0^2\right]+\frac{1}{2^2}\left[y_0^2+y_0\right]\to\\
y_2=[2+2+2^{-1}]+[1+2^{-1}]
$$
