15

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$ integers.

Thanks :)

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

user26857
  • 52,094
mathsnoob
  • 667
  • 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
  • @rschwieb Thanks for the edit. I think it looks familiar because maybe you've seen a problem of a similar structure? I haven't seen any on this site, but if you find any, please let me know? Thanks :) – mathsnoob Mar 19 '13 at 20:21
  • 2
    @gev, f is not necessarily bijective. – Biswanath Mar 19 '13 at 20:24
  • Oh yea, I must ask this. What does bijective and surjective and those terms mean? Thanks. – mathsnoob Mar 19 '13 at 20:25
  • Yes, you can't conclude that $f(0)=0$ from $n=0$, @gev. – Thomas Andrews Mar 19 '13 at 20:25
  • 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
  • @Biswanath, see the answer below, it explains why you can conclude f(0)=0. – gev Mar 19 '13 at 20:32
  • @rschwieb Nope, no luck for me either. But I'm sure this problem has occurred in many maths contests because it just looks like a typical olympiad question... Anyway thanks! :) – mathsnoob Mar 19 '13 at 20:32

3 Answers3

11

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$.

Dejan Govc
  • 17,007
  • 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
  • 1
    @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 00:11
  • 1
    @DejanGovc, could you explain why the usual argument claims $f(x)=cx$ is the only class of solutions to the rational Cauchy's functional equation? – Meow Mar 23 '13 at 13:30
  • 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
  • @DejanGovc Thanks; that's really quite elegant. – Meow Mar 23 '13 at 18:07
  • @DejanGovc But $tan(x)$ is also a periodic function having INFINITELY many values!! – Hamid Reza Ebrahimi Jan 08 '18 at 10:41
7

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$$

1

Let the given assertion be $P(m,n)$ $$P(0,n) \implies f(f(n))=n+f(0)$$ So, let's assume $f(a)=f(b)$ $$f(a)=f(b)\implies f(f(a))=f(f(b)) \Leftrightarrow a+f(0)=b+f(0) \Leftrightarrow a=b$$ That means that $f$ is injective (one-to-one), so $f(a)=f(b)\Leftrightarrow a=b$ Now, $$P(0,0)\implies f(f(0))=f(0) \Leftrightarrow f(0)=0$$ So, (by $P(0,n)$) $$f(f(n))=n$$ Now, $$P(m,f(n))\implies f(m+n)=f(m)+f(n)$$ This is a well-known functional equation called the Cauchy functional equation.

One way of dealing with it: $$\underbrace{f(n)+f(n)+\dots+f(n)}_\text{$k$ times}=f(\underbrace{n+n+\dots+n}_\text{k times})$$ $$\Leftrightarrow kf(n)=f(kn)$$ and putting $n=1$ we get $f(k)=kf(1)$ for all $k \geq 1$

Another way of dealing with it:

Let the conclusion above be $H(m,n)$ $$H(1,1)\implies f(2)=2f(1)$$ $$H(2,1)\implies f(3)=f(2)+f(1)=2f(1)+f(1)=3f(1)$$ $$H(3,1)\implies f(4)=f(3)+f(1)=3f(1)+f(1)=4f(1)$$ and so on, by simple induction, we can say that

$f(x)=xf(1)$ for all $x \geq 1$ and $f(0)=0$

So, for both ways, we need to extend it over the negative integers, by proving that $f$ is odd. Well, $$H(m,-m) \implies f(m)+f(-m)=0 \Leftrightarrow f(-m)=-f(m)$$ Or (another way) $$P(-f(n),n)\implies f(-f(n))+n=0 \Leftrightarrow f(-f(n))=-n$$ $$P(0,-f(n)) \implies f(f(-f(n)))=-f(n) \Leftrightarrow f(-n)=-f(n)$$ So, $f$ is odd, meaning that $f(x)=xf(1)$ applies for all integers $x$

Let $f(1)=c$ giving $f(x)=cx$, substituting in the original equation, we get $$cm+{c^2}n=cm+n$$ $$\Leftrightarrow c^2=1 \implies c=\pm 1$$ So, $$f(x)= \pm x$$

Anas A. Ibrahim
  • 1,884
  • 7
  • 15