$U_{n} + \lfloor \sqrt{U_{n}} \rfloor = k^{2}$ 
I've been stuck, I tried to prove it by extracting the explicit formula. I have found that $U_n=U_0+ n \times \lfloor \sqrt{U_0} \rfloor$
 A: For each number $u\in\mathbb N$, index it by a pair $(i,j)$:
$$\begin{align*}
i &= \left\lfloor \sqrt u\right \rfloor\\
j &\equiv u \pmod i, &&j\in\{1,2,3,\ldots, i\}\\
\end{align*}$$
For example, $9$ has index $(3,3)$, and $18$ has index $(4,2)$. This puts numbers in $i^2\le u < (i+1)^2$ into one of $i$ "buckets", depending on the remainder $\bmod i$.
The next number in the sequence after $u$ would be $u+\left\lfloor\sqrt u\right\rfloor = u+i$. There are two cases:

*

*If $i^2 \le u+i < (i+1)^2$, then $\left\lfloor\sqrt{u+i}\right\rfloor$ remains unchanged, and the "bucket" number also remains unchanged: $u+i \equiv u \equiv j \pmod i$.

*Otherwise, $u+i$ is equal to or above a new perfect square, i.e. $u+i \ge \left(\left\lfloor\sqrt u\right\rfloor+1\right)^2 = (i+1)^2$. In this case, $\left\lfloor\sqrt{u+i}\right\rfloor = i+1$.

For the second case, the new "bucket" number of $u+i$ will be $u+i\equiv j-1\pmod{i+1}$:
$$\begin{align*}
&\mod i:&\overbrace{u+i - (i+1)^2}^{\in[0,i)}&\equiv u-i^2-i-1\\
&&&\equiv \underbrace{j-1}_{\in[0,i)}\\
&&u+i-(i+1)^2 &= j-1\\
\therefore&\mod{i+1}: & u+i&\equiv j-1
\end{align*}$$

*

*If the "bucket" number $j-1 \equiv 0\pmod{i+1}$, then $u+i = (i+1)^2$ and is a perfect square.

*Otherwise $j-1$ is positive and less than the original $j$.

Along the sequence, each time a sequence term reaches a new perfect square, the "bucket" number will decrease by $1$,  eventually reduce to $0$. That term is a perfect square and satisfies the question.
