Balkan Olympiads 2009

Find all functions $f: \mathbb{N}^{*} \rightarrow \mathbb{N}^{*}$ such that for all positive integers $m$ and $n$,

$$
f\left(f^{2}(m)+2 f^{2}(n)\right)=m^{2}+2 n^{2}
$$
Injectivity is immediate. And, $(x+3)^{2}+2 x^{2}=(x+1)^{2}+2(x+2)^{2}$, so $f^{2}(x+3)+2 f^{2}(x)=f^{2}(x-1)^{2}+2 f^{2}(x+2)$. If we set $u_{n}=f^{2}(n)$, we have a linear recurrence relation on this sequence:

$$
u_{n+4}-2 u_{n+3}+2 u_{n+1}-u_{n}=0
$$

The associated polynomial is $X^{4}-2 X^{3}+2 X-1=(X-1)^{3}(X+1)$. Therefore, $u_{n}=a n^{2}+b n+c+(-1)^{n} d$ with $a, b, c, d$ being constants. Since $2 u_{1}+u_{5}=3 u_{3}$ (take $m=n=3$ and $m=1, n=5$ in the initial equation), we have $b=0$, and then we use the fact that $u_{n}$ is a square to deduce (exercise!) that $a$ is a square and that $c=d=0$. By substituting into the initial equation, we find $a=1$. Conversely, the identity is indeed a solution.