Prove that the sequence $a, f(a),\cdots$ contains at least one square of an integer 
Let $f(n) = n+\lfloor \sqrt{n}\rfloor$. Prove that for every positive integer $a$, the sequence $a, f(a),\cdots$ contains at least one square of an integer.


Can someone explain why in the solution below, $f^r(m)$ is a square for some r with $0\leq r\leq 2j$? Why is it $2j$ instead of $j$? From my understanding, the "excess" strictly decreases by 1 provided it's positive.


 A: Any natural number can be placeb between two consecutive perfect squares. Precisely, for any $m\in\Bbb N$ there is $k\in\Bbb N$ such that $k^2\leq m<(k+1)^2=k^2+2k+1$. Therefore each natural $m$ can be presented as $k^2+j$ where $0\leq j\leq 2k$. For example

*

*$40=6^2+4$ ($k=6$, $j=4$)

*$48=6^2+12$ ($k=6$, $j=12$)

*$49=7^2$ ($k=7$, $j=0$)

Now, all numbers are divided into two sets:
$$A=\{k^2+j:0\leq j\leq k\}\quad\text{and}\quad B=\{k^2+j:k< j\leq 2k\}.$$
It is shown that

*

*if $m\in B$ then $f(m)\in A$

*if $m\in A$ then either $m$ is a perfect square or $f^2(m)$ has smaller excess (decreases by $1$). Therefore is still in $A$ and after some iterations the excess must be zero, i.e. $m$ is a perfect square.

Example
Let $m=46\in B$ ($k=6,\ j=10$). Then:

*

*$f(m)=46+6=52$ ($k=7,\ j=3$, $f(m)\in A$).

*$f^3(m)=f(52+7)=59+7=66$ ($k=8$, $j=2$)

*$f^5(m)=f(66+8)=74+8=82$ ($k=9$, $j=1$)

*$f^7(m)=f(82+9)=91+9=100$ ($k=10$, $j=0$).

Now let's check the condition $0\leq r\leq 2j$. Let $E(a)$ be the excess of $a$. Choose any $m$ and put $E(m)=j$.

*

*If $m\in A$ then $E(f^2(m))=E(m)-1$, $E(f^4(m))=E(f^2(m))-1=E(m)-2$ and so on, so $E(f^{2j}(m))=E(m)-j=0$, so $r=2j$.

*If $m\in B$ then $f(m)\in A$ and $E(f(m))=j-k-1$. Therefore, from the previous point, $E(f^{1+2(j-k-1)}(m))=0$, so $r=2j-2k-1<3j$.

