Let $m$ be a natural number. Define $f(m) = m + \lfloor\sqrt{m}\rfloor$. Prove that at least one of the number among $m, f(m), f^2(m), \ldots$ is a perfect square. Here $f^k(m)$ denotes the composition of $f$ over itself $k$ times.
I tried the question, but the greatest integer along with square root is creating trouble.
Best Answer
Supposing $m$ is not a perfect square, then $m=n^2+k$, where $n^2$ is the largest perfect square less than $m$. Without loss of generality, if $k>n$ we can take $m_0=m-n$ and $k_0=k-n$, otherwise $m_0=m, k_0=k$.
Then we can see that $f^2(m_0) = n^2+k_0+2n = (n+1)^2+(k_0-1)$.
Taking $m_1=f^2(m_0)$ and $k_1=(k_0-1)$ we can see the same process applies relative to $(n+1)^2$ and so in a total of $2k_0$ applications of $f$ we will have a perfect square, $f^{2k_0}(m_0) = (n+k_0)^2$.
Additional observation: Note that once a square is found, $s_0^2 = f^d(m)$, the same process can be applied to $f^{d+1}(m) = s_0^2+s_0$, which will then give another perfect square at $f^{d+1+2s_0}(m) = (2s_0)^2$.
Thus there are an infinite number of perfect squares in the given sequence, of the form $(2^as_0)^2$, where $a$ is a non-negative integer. This also means there is at most one odd square in the sequence, which only occurs if $m_0$ is odd (or if $m$ itself is an odd square).