The domain of a function f is the set of natural numbers. The function is defined as follows:
$$f(n) =n+[\sqrt{n}] $$
Where $[x] $=nearest integer smaller than or equal to x. For example, $[$pi$]$ =3.
Prove that for every natural number m the following sequence contains at
least one perfect square
$$m, f(m), f^2 (m), f^3 (m)…….. $$
The notation $f^k$ denotes the function obtained by composing f with itself k times, e.g.,$f^2 = f ◦ f$.
My attempt:
I don't know what to say but I have just used numbers to put in the equation to verify. Other than this I am not able to think anything about it.
Best Answer
Let $n = m^2+k$ where $1 \le k \le 2m$.
Then
$\begin{array}\\ f(n) &=n+[\sqrt{n}]\\ &=m^2+k+[\sqrt{m^2+k}]\\ &=m^2+k+m\\ \end{array} $
If $1 \le k \le m$ then
$\begin{array}\\ f^{(2)}(n)=f(f(n)) &=m^2+k+m+[\sqrt{m^2+k+m}]\\ &=m^2+k+m+m\\ &=m^2+2m+k\\ &=(m+1)^2+k-1\\ \end{array} $
Therefore $f(f(n))$ is one closer to a square than $f(n)$. In particular, if $k=1$ then $f(f(n))$ is a square.
If $m+1 \le k \le 2m$ then
$\begin{array}\\ f^{(2)}(n)=f(f(n)) &=m^2+k+m+[\sqrt{m^2+k+m}]\\ &=m^2+2m+1+k-(m+1)+[\sqrt{m^2+2m+1+k-(m+1)}]\\ &=(m+1)^2+k-(m+1)+(m+1)\\ &=(m+1)^2+k\\ \end{array} $
and $k-(m+1) =(k-m)-1 \lt k-m$ so the difference between $k$ and the square below it decreases by $1$. Repeating this $m$ times brings it down where $k \le m$ (where "$m$" is the current square, not the original one) and the paragraph above applies.
In both cases, eventually $f^{(j)}(n) =\lfloor \sqrt{f^{(j)}(n)} \rfloor ^2 $.