6
$\begingroup$

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.

  • 0
    $f = 0$ and $f(n) = n$ are not the only solutions. Take for example $f(2n) = f(2n+1) = 2n$.2012-05-31

1 Answers 1

5

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.

  • 0
    @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$.2012-05-31