Croatian Mathematical Olympiad

We easily get $f(1)=1$, $f(2)=f(1)+f(1)=2$, $f(5)=f(4)+f(1)=5$, $f(20)=f(4)f(5)=20$ and $f(16)=f(20)-f(4)=16$. We prove the claim by complete mathematical induction, assuming it holds for all positive integers $m\le n$ ($P(m)$), and performing the induction step for $n+1$:

1) If $n$ is even, then $n+1=2k+1$ for some positive integer $k$. Note that $2(k^2+(k+1{)}^2)=(2k+1{)}^2+1$ and $k^2+(k+1{)}^2$ is odd, hence $$\begin{array}{rl}f((2k+1{)}^2)+1& =f((2k+1{)}^2+1)=f(2(k^2+(k+1{)}^2))\\ & =f(2)f(k^2+(k+1{)}^2)=2(f(k^2)+f((k+1{)}^2))\\ P(k),P(k+1)⟹& =2(k^2+(k+1{)}^2)=(2k+1{)}^2+1,\end{array}$$ i.e. $f((n+1{)}^2)=(n+1{)}^2$.

2) If $n$ is odd, then $n+1=2k$ for some positive integer $k$.

a) If $k$ is even, then $k^2+1$ is odd, and we get $$\begin{array}{rl}f((2k{)}^2)+4& =f((2k{)}^2+4)=f(4(k^2+1))\\ & =f(4)f(k^2+1)=4(f(k^2)+1)\\ P(k)⟹& =4(k^2+1)=(2k{)}^2+4,\end{array}$$ i.e. $f((n+1{)}^2)=(n+1{)}^2$.

b) If $k$ is odd, then $k^2+4$ is odd as well, hence $$\begin{array}{rl}f((2k{)}^2)+16& =f((2k{)}^2+16)=f(4(k^2+4))\\ & =f(4)f(k^2+4)=4(f(k^2)+4)\\ P(k)⟹& =4(k^2+4)=(2k{)}^2+16,\end{array}$$ i.e. $f((n+1{)}^2)=(n+1{)}^2$.