Find all functions $f: \mathbb{Z}_{\ge 0}\rightarrow \mathbb{Z}_{\ge 0}$ such that $f(f(m)+f(n))=m+n.$

My idea was to set $m_0$ such that $f(m_0)=0$ and then:

$$ f(f(m_0)+f(n))=f(0+f(n))=f(f(n))=m_0+n$$

Then to set $m=n$:

$$ f(2f(n))=2n $$

But here I run out of ideas, as I don't know what to do to get $f(n)$ instead of $f(f(n))$ or $f(2f(n))$. Could somebody show me some hints?

  • $\begingroup$ Maybe you can try to show that $f$ is a bijection ? Surjectivity is really easy, and injectivity comes with a trick. Once you have that, maybe you can get some more ideas $\endgroup$ Mar 11 '17 at 23:21
  • $\begingroup$ Hi OP! I took your first result and played with it a bit: $f(f(n)) = m_0 + n$ leads to, after taking $n = 0$, $f(0) = 2m_0$. Then we take $f(f(f(n)) + f(0)) = f(n) + 0$, and get $f(m_0 + (n + 2m_0)) = f(n)$. $\endgroup$
    – Chris
    Mar 11 '17 at 23:31

The surjectivity is pretty much trivial. For the injectivity assume that $f(m) = f(n)$, then there exists (from surjectivity) $f(m_1) = m$, $f(n_1) = n$ and $f(k) = 0$. So we have:

$$m_1 + k = f(f(m_1) + f(k)) = f(m) = f(n) = f(f(n_1) + f(k)) = n_1 + k \implies m_1 = n_1 \implies m=n$$

Therefore the function is bijective. Now assume that $f(k) = 0$. Then:

$$f(f(k) + f(k)) = 2k = f(f(2k) + f(0))$$

From the bijectivity we have: $f(2k) + f(0) = f(k) + f(k) = 0$. But as $f(x) \ge 0 $ we get that $f(0) = 0$. Finally:

$$f(f(m) + f(n)) = m+n =f(f(m+n) + f(0)) \implies f(m+n) = f(m) + f(n)$$

The last equation can be easily solved using induction and later you can find a suitable value for $f(1)$.


As Max noted in his comment, surjectivity is straightforward to prove, so I'll leave that one for you. As for injectivity, if we have $f(m) = f(n)$, then $f(f(m) + f(n)) = f(f(n) + f(n))$, and so $m + n = 2n$, which says $m = n$. Therefore $f$ is a bijection.

Taking $f(m_0) = 0$, we obtain $f(f(n)) = m_0 + n$ and $f(0) = 2m_0$, so that $f(f(f(n)) + f(0)) = f(n) = f(3m_0 + n).$ Clearly bijectivity implies $m_0 = 0$, so $f(0) = 0$. Then $f(f(m+n) + f(0)) = f(f(m) + f(n)) = m+n$ (just as Stefan showed); thus, because $f$ is injective, $f(m) + f(n) = f(m + n)$. Thus $f(n) = nf(1)$, and so surjectivity requires $f(1) = 1$, and thus $f(n) = n$.


If $f(m)=f(n)$ then $m=n$

There is a solution to $f(x)=n$, for every $n$

Write $m_2,m_3,m_4,...$ in terms of $m_0$ and $m_1$


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.