$U_{n} + \lfloor \sqrt{U_{n}} \rfloor = k^{2}$

Question

I've been stuck, I tried to prove it by extracting the explicit formula but i got nowhere.

Answer 1

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.