$f(n)=n+\lfloor\sqrt{n}\rfloor$. Prove for all $m\in \mathbb{N}$, the sequence $m,f(m),f(f(m)),..$ contains a perfect square

Question

Would anyone verify my solution for the following problem?

$f(n)=n+\lfloor \sqrt{n} \rfloor$. Prove for every positive integer $m$, the sequence $$m,f(m),f(f(m)),...$$ contains a perfect square.

---

Claim $1$.

For all $m$ in the form of $m=n^2+b$ where $0\leq b<2n+1,n>b-1 \implies m>(b-1)^2+b$, the sequence contains a perfect square

Proof of Claim $1$

We will use strong induction on $b$:

1. For $b=1$, $n^2<m=n^2+1<(n+1)^2, n^2<n^2+n+1<(n+1)^2$. Thus $f(m)=n^2+n+1, f^{2}(m)=n^2+2n+1=(n+1)^2$.

2. Assume that it's true for $b=1,2,...,k$. For $m=n^2+k+1$ with $n>2k$, $f(m)=n^2+n+k+1$. $f^2(m)=n^2+2n+k+1=(n+1)^2+k$. We are done by induction.

End of Proof of Claim $1$

By Claim 1, all $m=n^2+b$ where $m>(b-1)^2+b$ is valid. For $m$ in the form of $m^2+b$ where $m <(b-1)^2+b$, we can take $m=(b-1)^2+b-1, ...$ (decreasing)

---

The last part looks kinda weird. If the last part is true that's fine (However, is there a better way to finish the last part of the problem?).

Answer 1

Your solution seems correct to me.But I think you could write your argument in a different way.

Here goes my solution(which is much similar to yours)::

Let $g(m)$ be defined as $m-\text{the largest perfect square smaller than m}$

We will prove by induction that for any positive integer $g(m)$ the given condition holds.

Base case:$g(m)=1$ aka $m=n^2+1$, Then $f^2(m)=n^2+n+1$ if $f(m)$ is not a square.

Now,assume the condition holds for $g(m)=1,\cdots,k$.

$\textbf{Case 1}:$

Now,If $m=n^2+k$ with $k<n+1$ Then,$f^2(m)=f(n^2+n+k)=(n+1)^2+(k-1)$ (the only exception is when $n^2+n+k$ itself is a perfect square).

But $g(f^2(m))=k-1$ for which the condition holds by our inductive hypothesis.

$\textbf{Case 2}$

If $k>n+1$ (k=n+1 would make f(m) a perfect square)

$f^2(m)=(n+1)^2+k$.

Here $n$ has become $n+1$ and $g(m)$ has remained $k$ where new $m$ is $f^2(m)$.

So,either in the next steps $g(m)$ decreases or stays the same.

But since $n$ is increasing but k remains same,at some point $k$ has to be $<n+1$ and then by the first part of our inductive argument $k$ will be reduced to $k-1$ for which the inductive hypothesis says the condition holds.

So,we are done.