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

  • 1
    $\begingroup$ This looks very familiar. Possibly there is an answer on the site somewhere :) $\endgroup$
    – rschwieb
    Mar 19 '13 at 20:11
  • 1
    $\begingroup$ Usually, the idea for such problems is to look at $f(0)$ then $f(f(0))$ etc. $\endgroup$ Mar 19 '13 at 20:14
  • 1
    $\begingroup$ 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$ $\endgroup$
    – gev
    Mar 19 '13 at 20:16
  • 2
    $\begingroup$ @gev, f is not necessarily bijective. $\endgroup$
    – Biswanath
    Mar 19 '13 at 20:24
  • 1
    $\begingroup$ @mathsnoob Definitely simliar, maybe identical. Unfortunately I couldn't find it by searching. You might try for yourself, maybe you will have luck. $\endgroup$
    – rschwieb
    Mar 19 '13 at 20:30

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

  • $\begingroup$ I think I understand your answer, like the first time I understood any functions! XD Thanks! :) $\endgroup$
    – mathsnoob
    Mar 19 '13 at 20:34
  • $\begingroup$ Did you not assume the axiom of choice here ?? $\endgroup$
    – mick
    Mar 19 '13 at 20:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dejan Govc
    Mar 19 '13 at 23:44
  • 1
    $\begingroup$ @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? $\endgroup$
    – Meow
    Mar 23 '13 at 13:30
  • 1
    $\begingroup$ @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$. $\endgroup$
    – 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$$

  • 1
    $\begingroup$ But most constants do not work. $\endgroup$ Mar 19 '13 at 20:32

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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