Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.