Prove that the sequence $a, f(a),\cdots$ contains at least one square of an integer

Question

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.

Answer 1

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$.