# $f(m + f(n)) = f(f(m)) + f(n)$

I found this one in the list of IMO'96 (3) problems and decided to have a go at it, but could not complete the solution. So $m$ and $n$ are non-negative integers and $f$ takes values in the same set:

$$f(m + f(n)) = f(f(m)) + f(n)$$

Let $m=n=0$: $$f(f(0))=f(f(0))+f(0)$$ hence $$f(0)=0$$ Now let $m=0$: $$f(f(n))=f(n)$$ therefore: $$f(m+f(n))=f(m)+f(n)$$ Now consider the following possibilities

1) $f(m)=f(n) \implies m=n$ $$f(m+f(n))=f(m)+f(n)$$ $$f(n+f(m))=f(n)+f(m)$$ By symmetry of the RHS: $$f(m+f(n))=f(n+f(m))$$ Hence, by assumption $$m+f(n)=n+f(m)$$ $$f(n)-n=f(m)-m$$ Since the two sides are independent they must be both equal to a constant $$f(n)-n=C$$ $$f(0)=0 \implies C=0 \implies f(n)=n$$ 2) It is the second part where I got confused. I assumed $f(m)=f(n)$ where $m \ne n$, so that $$f(m+f(n))=2f(n)$$ then figure that since RHS does not depend on $m$ whereas LHS does, then $f=C$ and deduced from the original equation that $C$ must be 0. But then I relayed that in fact here I have some particular values of $m$ and $n$ and not just something arbitrary. If anyone can point me in the right direction, I would be grateful.

-
The RHS does depend on $m$, in a sense. In this argument at this point, you are not free to let $n$ take on any value; $n$ can only take on values that are in the pre-image of $f(m)$. So you can't conclude that $f$ is constant, but rather that $f$ is constant on subsets of $\mathbb{N}_0$ where the output of $f$ is fixed - a tautology. – alex.jordan May 31 '12 at 19:21
$f = 0$ and $f(n) = n$ are not the only solutions. Take for example $f(2n) = f(2n+1) = 2n$. – marlu May 31 '12 at 19:36

If $f$ is a solution to $f(m+f(n)) = f(f(n)) + f(m)$ then either $f \equiv 0$ or there is some $k\in\mathbb N$ and some $a_0,\ldots,a_{k-1} \in \mathbb N_0$ with $a_0 = 0$ s.t. $f(kn+r) = k(n+a_r)$ for all $n\in \mathbb N_0, 0 \leq r < k$.

It is easy to verify that these functions are indeed solutions of the functional equation. To prove that every solution is of this kind, we first make some observations about fixed points.

Claim: Let $f$ be a solution and denote by $F$ the set of fixed points of $f$, i.e. $F = \{ n\in \mathbb N_0 : f(n) = n \}$. Then the following statements hold:

1. $0 \in F$
2. $F$ is closed under addition, i.e. if $x,y\in F$, then also $x+y \in F$.
3. If $x \in F$ and $x+y \in F$ , then also $y \in F$.
4. $F = k\mathbb N_0$ for some $k \in \mathbb N_0$.

Proof: (1) follows from $f(0) = 0$. If $x,y\in F$ then from $f(x+f(y)) = f(x)+f(y)$ we get $f(x+y) = x+y$, hence $x+y \in F$. If $x,x+y\in F$ then $$y+x = f(y+x) = f(y+f(x)) = f(y)+f(x) = f(y) + x,$$ hence $f(y) = y$. (4) now follows from the previous statements: If $0$ is the only fixed point then $F = \{0\} = 0\mathbb N_0$ and we are finished. Otherwise, there is a smallest non-zero fixed point $k$. By (2), $k\mathbb N_0 \subseteq F$. If $x$ is any other fixed point then write $x = kn+r$ with $n\in \mathbb N_0$ and $0 \leq r < k$. By (3), we have $r \in F$. But $k$ is the smallest non-zero fixed point and $r < k$, so $r = 0$ and $x = kn \in k\mathbb N_0$. (This was basically the proof that $\mathbb Z$ is a principal ideal domain.)

Now observe that $f(\mathbb N_0) \subseteq F$, since $f(f(n)) = f(n)$ for all $n$. Therefore, if $F = \{0\}$ then $f(n) = 0$ for all $n$, i.e. $f$ is constantly zero. Otherwise, $F = k\mathbb N_0$ for some non-zero $k$. Now let $a_r' := f(r)$ for $0 \leq r < k$. Then $a_0' = 0$, and for all $n \in \mathbb N_0$ and $0\leq r < k$ we have $$f(kn+r) = f(r + f(kn)) = f(r) + f(kn) = f(r) + kn = kn + a_r'.$$ Furthermore, $kn+a_r' \in f(\mathbb N_0) \subseteq k\mathbb N_0$, hence $k|a_r'$. Write $a_r' = k a_r$, then $f(kn+r) = k(n+a_r)$, as claimed.

-
I can't help thinking there are some redundant steps in (1), but many thanks indeed. I guess this is the level of detail expected at the IMO level – Valentin May 31 '12 at 20:55
Can we just say that $f(0)=0$, and that $g:=f-\operatorname{id}$ is periodic? – alex.jordan May 31 '12 at 20:57
@alex.jordan: $g = f-\operatorname{id}$ is periodic, but in addition $g(m) \equiv -m \pmod k$. Also, for $f$ to have values in $\mathbb N_0$, you need further restrictions on $g$. – marlu May 31 '12 at 21:11