Solve $X_n=\lfloor \sqrt{X_n} \rfloor+X_{n-1}$

Question

How do I solve $X_n=\lfloor \sqrt{X_n} \rfloor+X_{n-1}$? The initial terms are $1,2,3,5,7,10,13,17,21,26,31$. A search on oeis.org/ gave $\lfloor n/2 \rfloor\cdot\lceil n/2 \rceil$ + 1 which should be proven by induction. Is there a different approach?

Answer 1

The difference equation \begin{align} x_{n} = \lfloor \sqrt{x_{n}} \rfloor + x_{n-1}, \end{align} where $x_{0}=1 $ and $x_{1}=2$ can, upon writing out several terms, ie $x_{2}$, $x_{3}$, $x_{4}$, and so on can the given set of values stated. It is without much difficulty to show that the difference equation for $x_{n}$ can also be seen as \begin{align} a_{n} = a_{n-2} + n \end{align} where $a_{o}=1$ and $a_{2}=2$. The set generated by $a_{n}$ is $a_{n} \in \{ 1,2,3,5,7,10,13,17,21,26,31, \cdots \}$. Now the even and odd values can be considered and yields \begin{align} a_{2n} = n^{2} +1 \end{align} for $n\geq 0$ for the even case and \begin{align} a_{2n+1} = n^{2} + n+1 = n(n+1) + 1 \end{align} for the odd case. From the two cases it can readily be sen that the general result is given by \begin{align} a_{n} = \left\lfloor \frac{n}{2} \right\rfloor \cdot \left\lceil \frac{n}{2} \right\rceil + 1. \end{align}