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 am a real newbie when it comes to funtions, and I don't understand what is supposed to happen or what I'm supposed to find when I get given an olympiad type question concerning functions. Could you help me out by solving, proving and explaining (it would be nice if you could) the following question? Thanks, any help is appreciated.

I think one of my teachers mentioned something about plugging in $m=0$ or something, but... Bleh, I don't know. Please help?

This question is taken from the South African Mathematics Olympiad of 1997.

Find all functions $f: \Bbb Z \to \Bbb Z $ which satisfy

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

for all $m$, $n$ which are integers.

Thanks :)

Thanks to everyone who helped me with this question :) I'm now one step further in my life...

share|improve this question
1  
This looks very familiar. Possibly there is an answer on the site somewhere :) –  rschwieb Mar 19 '13 at 20:11
1  
Usually, the idea for such problems is to look at $f(0)$ then $f(f(0))$ etc. –  Thomas Andrews Mar 19 '13 at 20:14
1  
Taking $n=0$ gives us $f(m)=f(m+f(0))$ or $f(0)=0$. Next, taking $m=0$ we'll have $f(f(n))=n$ –  gev Mar 19 '13 at 20:16
2  
@gev, f is not necessarily bijective. –  Biswanath Mar 19 '13 at 20:24
1  
@mathsnoob Definitely simliar, maybe identical. Unfortunately I couldn't find it by searching. You might try for yourself, maybe you will have luck. –  rschwieb Mar 19 '13 at 20:30

2 Answers 2

up vote 10 down vote accepted

Plugging in $n=0$, we get that $$f(m+f(0))=f(m)\tag{1}$$ must hold for all $m\in\mathbb Z$. There are now two possibilities.

Case 1. $f(0)\neq 0$.

In this case, the equation $(1)$ tells us that $f$ is a periodic function. But this would necessarily imply that $f$ is bounded (since it would have to take only finitely many values), i.e. there exists a positive integer $M$ such that $-M\leq f(x)\leq M$ holds for all $x\in\mathbb Z$. But this is impossible: plugging in $n = 2M+1$ into the equation would then yield $$2M\geq f(m+f(2M+1))-f(m)=2M+1$$ which is absurd; therefore this case does not occur.

Case 2. $f(0) = 0$.

In this case, plug $m=0$ into the original equation. This tells us that $$f(f(n))=n\tag{2}$$ must hold for all $n\in\mathbb Z$. Plugging in $f(n)$ instead of $n$ into the original equation and using $(2)$ then tells us that $$f(m+n)=f(m)+f(n)$$ holds for all $m,n\in\mathbb Z$. Using the usual argument, this implies that $f$ is of the form $f(x) = c x$ for some constant $c$. By $(2)$, this constant is either $1$ or $-1$. Both choices satisfy the original equation.

Conclusion. The solutions to the equation are given precisely by $f(x)=x$ and $f(x) =-x$.

share|improve this answer
    
I think I understand your answer, like the first time I understood any functions! XD Thanks! :) –  mathsnoob Mar 19 '13 at 20:34
    
Did you not assume the axiom of choice here ?? –  mick Mar 19 '13 at 20:57
    
@mick: I always assume it, but as far as I can tell, I didn't use it here. If your question concerns the solution of Cauchy's functional equation: the only solutions over integers are of the form I mentioned, which can be seen using induction. The "strange" solutions occur when solving the equation over the reals. –  Dejan Govc Mar 19 '13 at 23:44
    
Oh you are right, I was thinking in terms of reals. Sorry. –  mick Mar 20 '13 at 0:11
1  
@Alyosha: sure. Suppose $f(x+y)=f(x)+f(y)$ for all $x,y\in\mathbb Z$. First of all this implies $f(0)=f(0)+f(0)$ by taking $x=y=0$; in other words, $f(0)=0$. Now, we let $c:=f(1)$. Then for $x$ a positive integer, we have $f(x)=f(1+1+\ldots+1)=f(1)+f(1)+\ldots+f(1)=c+c+\ldots+c = cx$ (here, each sum with "$\ldots$" has $x$ terms). Now, assume $x$ is a negative integer. In this case, $f(x)+f(-x)=f(x+(-x))=f(0)=0$. Therefore $f(x)=-f(-x)=-c(-x)=cx$, where the second equality comes from the fact that $-x$ is now a positive integer, which is a case we already know. Therefore $f(x)=cx$ for all $x$. –  Dejan Govc Mar 23 '13 at 17:36

Clearly, $f(n) = \pm n$ is a solution. Now let us see if there are other solutions. Plug in $n=0$. We then have $$f(m+f(0)) = f(m)$$ If $f(0) \neq 0$, we then have $f$ to be periodic with period $f(0)$. This means $f(n)$ an take only finitely many values. Plugging $m=0$, we get that $$f(f(n)) = n + f(0)$$ which takes infinitely many values contradicting the previous fact. Hence, $f(0) = 0$. Now plug in $m=0$ to get $$f(f(n)) = n$$ Hence, we have $$f(m+n) = f(m+f(f(n))) = f(m) + f(n)$$ This means $$f(m) = \text{constant} \times m = km$$ This means $$f(m+f(n)) = f(m) + n \implies f(m+kn) = km+n \implies km + k^2n = km +n \implies k^2n = n$$ Since this is true for all $n$, we have $k^2=1$. Hence, $k = \pm 1$. Hence, the only solutions are $$f(n) = \pm n$$

share|improve this answer
1  
But most constants do not work. –  Ross Millikan Mar 19 '13 at 20:32

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.