49th International Mathematical Olympiad Spain

The given conditions determine $f$ uniquely on the positive integers. The signs of $f(1),f(2),\dots$ seem to change quite erratically. However, values of the form $f\left(2^n-t(m)\right)$ are sufficient to compute directly any functional value. Indeed, let $n>0$ have base $2$ representation $n=2^{a_0}+2^{a_1}+\cdots +2^{a_k},a_0>a_1>\cdots >a_k\ge 0$, and let $n_j=2^{a_j}+2^{a_{j-1}}+\cdots +2^{a_k},j=0,\dots ,k$. Repeated applications of the recurrence show that $f(n)$ is an alternating sum of the quantities $f\left(2^{a_j}-t\left(n_{j+1}\right)\right)$ plus $(-1{)}^{k+1}$. (The exact formula is not needed for our proof.)

So we focus attention on the values $f\left(2^n-1\right),f\left(2^n-2\right)$ and $f\left(2^n-3\right)$. Six cases arise; more specifically, $t\left(2^{2k}-3\right)=2$, $t\left(2^{2k}-2\right)=1$, $t\left(2^{2k}-1\right)=3$, $t\left(2^{2k+1}-3\right)=1$, $t\left(2^{2k+1}-2\right)=3$, $t\left(2^{2k+1}-1\right)=2$.

Claim. For all integers $k\ge 0$ the following equalities hold: $$\begin{array}{lll}f\left(2^{2k+1}-3\right)=0,& f\left(2^{2k+1}-2\right)=3^k,& f\left(2^{2k+1}-1\right)=-3^k,\\ f\left(2^{2k+2}-3\right)=-3^k,& f\left(2^{2k+2}-2\right)=-3^k,& f\left(2^{2k+2}-1\right)=2\cdot 3^k\end{array}$$

Proof. By induction on $k$. The base $k=0$ comes down to checking that $f(2)=-1$ and $f(3)=2$; the given values $f(-1)=0,f(0)=1,f(1)=-1$ are also needed. Suppose the claim holds for $k-1$. For $f\left(2^{2k+1}-t(m)\right)$, the recurrence formula and the induction hypothesis yield $$\begin{array}{rl}& f\left(2^{2k+1}-3\right)=f\left(2^{2k}+(2^{2k}-3)\right)=f\left(2^{2k}-2\right)-f\left(2^{2k}-3\right)=-3^{k-1}+3^{k-1}=0,\\ & f\left(2^{2k+1}-2\right)=f\left(2^{2k}+(2^{2k}-2)\right)=f\left(2^{2k}-1\right)-f\left(2^{2k}-2\right)=2\cdot 3^{k-1}+3^{k-1}=3^k,\\ & f\left(2^{2k+1}-1\right)=f\left(2^{2k}+(2^{2k}-1)\right)=f\left(2^{2k}-3\right)-f\left(2^{2k}-1\right)=-3^{k-1}-2\cdot 3^{k-1}=-3^k.\end{array}$$ For $f\left(2^{2k+2}-t(m)\right)$ we use the three equalities just established: $$\begin{array}{rl}& f\left(2^{2k+2}-3\right)=f\left(2^{2k+1}+(2^{2k+1}-3)\right)=f\left(2^{2k+1}-1\right)-f\left(2^{2k+1}-3\right)=-3^k-0=-3^k,\\ & f\left(2^{2k+2}-2\right)=f\left(2^{2k+1}+(2^{2k+1}-2)\right)=f\left(2^{2k+1}-3\right)-f\left(2^{2k}-2\right)=0-3^k=-3^k,\\ & f\left(2^{2k+2}-1\right)=f\left(2^{2k+1}+(2^{2k+1}-1)\right)=f\left(2^{2k+1}-2\right)-f\left(2^{2k+1}-1\right)=3^k+3^k=2\cdot 3^k.\end{array}$$ The claim follows.

A closer look at the six cases shows that $f\left(2^n-t(m)\right)\ge 3^{(n-1)/2}$ if $2^n-t(m)$ is divisible by $3$, and $f\left(2^n-t(m)\right)\le 0$ otherwise. On the other hand, note that $2^n-t(m)$ is divisible by $3$ if and only if $2^n+m$ is. Therefore, for all nonnegative integers $m$ and $n$, (i) $f\left(2^n-t(m)\right)\ge 3^{(n-1)/2}$ if $2^n+m$ is divisible by $3$ ; (ii) $f\left(2^n-t(m)\right)\le 0$ if $2^n+m$ is not divisible by $3$ .

One more (direct) consequence of the claim is that $\left|f\left(2^n-t(m)\right)\right|\le \frac{2}{3}\cdot 3^{n/2}$ for all $m,n\ge 0$.

The last inequality enables us to find an upper bound for $|f(m)|$ for $m$ less than a given power of $2$. We prove by induction on $n$ that $|f(m)|\le 3^{n/2}$ holds true for all integers $m,n\ge 0$ with $2^n>m$.

The base $n=0$ is clear as $f(0)=1$. For the inductive step from $n$ to $n+1$, let $m$ and $n$ satisfy $2^{n+1}>m$. If $m<2^n$, we are done by the inductive hypothesis. If $m\ge 2^n$ then $m=2^n+k$ where $2^n>k\ge 0$. Now, by $\left|f\left(2^n-t(k)\right)\right|\le \frac{2}{3}\cdot 3^{n/2}$ and the inductive assumption, $$|f(m)|=\left|f\left(2^n-t(k)\right)-f(k)\right|\le \left|f\left(2^n-t(k)\right)\right|+|f(k)|\le \frac{2}{3}\cdot 3^{n/2}+3^{n/2}<3^{(n+1)/2}$$ The induction is complete.

We proceed to prove that $f(3p)\ge 0$ for all integers $p\ge 0$. Since $3p$ is not a power of $2$, its binary expansion contains at least two summands. Hence one can write $3p=2^a+2^b+c$ where $a>b$ and $2^b>c\ge 0$. Applying the recurrence formula twice yields $$f(3p)=f\left(2^a+2^b+c\right)=f\left(2^a-t\left(2^b+c\right)\right)-f\left(2^b-t(c)\right)+f(c)$$ Since $2^a+2^b+c$ is divisible by $3$, we have $f\left(2^a-t\left(2^b+c\right)\right)\ge 3^{(a-1)/2}$ by (i). Since $2^b+c$ is not divisible by $3$, we have $f\left(2^b-t(c)\right)\le 0$ by (ii). Finally $|f(c)|\le 3^{b/2}$ as $2^b>c\ge 0$, so that $f(c)\ge -3^{b/2}$. Therefore $f(3p)\ge 3^{(a-1)/2}-3^{b/2}$ which is nonnegative because $a>b$.