Prove that the expression is a perfect square

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

The case where $m$ is a perfect square is trivial. Else there's a $k$ with $k^2 < m < (k+1)^2$. Define $r(m)= m - k^2$ and $s(m) = m - k - k^2$. We show that either $r$ or $s$ monotonically decreases with applications of $f^2$, that is, $f$ applied twice.

There are two cases:

• If $m + k < (k + 1)^2$ then $f^2(m) = m + 2k = k^2 + r - 1 + 2k + 1 = (k+1)^2 + r(m) - 1$. So the error is now $r(f^2(m)) = r(m) - 1$.
• If $m + k = (k+1)^2$ then we're done, so assume $m + k > (k+1)^2$. Then $f^2(m) = m + 2k + 1 = s(m) +k + k^2 +2k + 1 = (s(m) - 1) + (k+1) + (k+1)^2$. So the error is now $s(f^2(m)) = s(m) - 1$. Since $s$ decreases by $1$ each time, eventually we'll get that $s = 1$ and so applying $f$ again will give us the next square.