<s>[INST] $f(m^2 + f(n)) = f(m)^2 + n$ for all natural numbers Find all functions such that $$ f(m^2 + f(n)) = f(m)^2 + n$$ for all natural numbers (1,2,3,4,..)
I have been stuck on this problem. 
I have tried to set f(1) = k, however, did not make any progress.
 [/INST] Let $P(m, n)$ denote $f(m^2+f(n)) = f(m)^2 + n$. Note that
\begin{align*}
P(1, y) \implies f(1+f(y)) &= f(1)^2 + y\\
\implies P(f(x), 1+f(y)) \implies f(f(x)^2 + f(1)^2 + y) &= f(f(x))^2 + 1 + f(y) \qquad (1)\\
P(x, y) \implies f(x^2+f(y)) &= f(x)^2 + y\\
P(f(1), x^2+f(y)) \implies f(f(x)^2 + f(1)^2 + y) &= f(f(1))^2 + x^2 + f(y) \qquad (2)\\
(1), (2)\implies f(f(x))^2 &= x^2 + c
\end{align*}
where $c = f(f(1))^2 - 1$. Hence, $x^2 + c$ is a perfect square for any positive integer $x$, so $c=0$ (otherwise, you can choose $x > c$ such that $x^2 + c < x^2 + x < (x+1)^2$, leading to a contradiction).
Hence, $f(f(x)) = x$. Therefore
$$P(1, f(x)) \implies f(x+1) = f(x) + f(1)^2$$
so $f(x) = f(1)^2x + (f(1) - f(1)^2)$. Since 
$$x = f(f(x)) = f(1)^4x + f(1)^2(f(1)-f(1)^2) + (f(1) - f(1)^2)$$
we must have $f(1) = 1$, so $f(x) = x$.
We can verify this to check it works, so we're done.
</s>