SELECTION TESTS FOR THE 2019 BMO AND IMO

The required functions are $f(n)=k{n}^2$, where $k$ is a non-negative integer — these clearly satisfy the condition in the statement.

Conversely, let $f$ be a function satisfying the condition in the statement. Setting $(a,b,c,d)=(n,n,n,n)$ in the functional relation yields $f(2n)=4f(n)$ for all $n$. In particular, $f(0)=0$ and $f(2)=4k$, where $k=f(1)$.

Setting successively $(a,b,c,d)=(n^2,1,n,n)$, $(a,b,c,d)=(n^2,2,2n,0)$ and $(a,b,c,d)=(n^2+1,1,n+1,n-1)$ in the functional relation yields $$\begin{array}{rl}f(n^2+1)& =f(n^2)+k+2f(n),\\ f(n^2+2)& =f(n^2)+4k+f(2n)=f(n^2)+4k+4f(n),\\ f(n^2+2)& =f(n^2+1)+k+f(n+1)+f(n-1).\end{array}$$ Subtraction of the second relation above from the sum of the other two yields $f(n+1)=2f(n)-f(n-1)+2k$.

---

Alternative solution.

As in the first solution, consider a function $f$ satisfying the condition in the statement, and establish that $f(2n)=4f(n)$, for all $n$; in particular, $f(0)=0$.

We now show by induction on $m$ that $f(mn)=m^{2}f(n)$ for all $n$. By the preceding, this is clearly the case if $m=0,1,2$. For the induction step, let $m>2$.

Since $\sqrt{m}<m$, if $m$ is a square, the conclusion follows by the induction hypothesis: $f(mn)=f(\sqrt{m}(\sqrt{m}n))=mf(\sqrt{m}n)=m^{2}f(n)$.

Otherwise, use Lagrange's four-square theorem to write $m=A+B$, where $A$ and $B$ are positive integers, each of which is a sum of two squares. Recall that if each factor of a product is a sum of two squares, then so is the product (use standard identities such as $(w^2+x^2)(y^2+z^2)=(wy+xz{)}^2+(wz-xy{)}^2$ repeatedly), to write $2AB=(1^2+1^2)AB=C^2+D^2$ for some non-negative integers $C$ and $D$. Clearly, $A<m$ and $B<m$; $C\le \sqrt{2AB}\le (A+B)/\sqrt{2}=m/\sqrt{2}<m$, and similarly, $D<m$. Setting $a=An,b=Bn,c=Cn$ and $d=Dn$ in the functional relation and applying the induction hypothesis completes the induction step: $$\begin{array}{rl}f(mn)& =f((A+B)n)=f(An)+f(Bn)+f(Cn)+f(Dn)\\ & =A^{2}f(n)+B^{2}f(n)+C^{2}f(n)+D^{2}f(n)=(A^2+B^2+C^2+D^2)f(n)\\ & =(A^2+B^2+2AB)f(n)=(A+B{)}^{2}f(n)=m^{2}f(n),\end{array}$$ for all non-negative integers $n$.

Consequently, $f(mn)=m^{2}f(n)$ for all $m$ and all $n$. Setting $n=1$ and $k=f(1)$ concludes the proof.