# Find all functions $f:\mathbb N\to\mathbb N$ such that $f\left(f(m)+f(n)\right)=m+n$, for all $m,n \in\mathbb N$.

Find all functions $$f:\mathbb N\to\mathbb N$$ such that $$f\left(f(m)+f(n)\right)=m+n$$, for all $$m,n \in\mathbb N$$.

I did not get any idea. I was just plugging out values for $$m=n=1$$ and so on no idea.

• Does ${\mathbb N}$ contain $0$? Feb 25 at 3:50
• Have you found a candidate function? What did you learn from plugging in values? Did you determine any? Feb 25 at 4:13
• What is a candidate function? also I di not get any by plugging in values. I was not able to determine any value Feb 25 at 4:16
• Can you think of some easy examples of $f$ that satisfy the equation, for example constant/linear ones? Feb 25 at 4:19
• the identity function satisfies this relation. also, it can’t be continuous since it’s not constant if that helps. also, if $0$ is in the natural numbers here, the the function is bijective, where we have to have $0$ map to $0$, or else it’s not well defined. continuing the assumption that $0$ is allowed, then $f(f(x))=x$ so $f$ is an involution and is it’s own inverse. Feb 25 at 10:38

Here, we assume $$\mathbb N$$ doesn't contain $$0$$, although the analysis should be pretty similar in the case where $$0\in\mathbb N$$.

Firstly, if $$f(x)=f(y)$$, then $$2x=f(2f(x))=f(2f(y))=2y,$$ so $$x=y$$; i.e., $$f$$ is injective. Now, consider any $$a,b,c\in\mathbb N$$ with $$a+b>c$$. Then $$f(f(a)+f(b))=a+b=c+(a+b-c)=f(f(c)+f(a+b-c)),$$ which implies that $$f(a)+f(b)=f(c)+f(a+b-c).$$ In particular, let $$f(1)=t$$ and $$f(2)=t+u$$. We claim that $$f(n)=t+u(n-1)$$ for all $$n$$, which can be proven by strong induction. It holds for $$n\in\{1,2\}$$, and for $$n\geq 3$$, $$f(n)+f(1)=f(2)+f(n-1),$$ which implies $$f(n)=f(n-1)+f(2)-f(1)=t+u(n-2)+t+u-t=t+u(n-1),$$ as desired. This means that $$m+n=f(f(m)+f(n))+f(2t+u(m+n-2))=t+u(2t+u(m+n-2)).$$ Since $$u\geq 0$$, we must have $$u=1$$, since the left side is $$m+n$$ and the right side is $$u^2(m+n)$$ plus some constant independent of $$m$$ and $$n$$. Then, we need $$m+n=t+2t+m+n-2,$$ which gives $$t=1$$. As a result, the only working function is the identity.

This is not an answer, mostly just results I found interesting, feel free to edit this post to complete it.

I'm going to assume there's no $$0$$ in $$\mathbb{N}$$ (if there was then the function would not be well-defined unless $$f(0)=0$$, if $$0 \mapsto e \not=0$$ then $$2e \mapsto 0$$ and then $$0\color{red}{\mapsto} 4e \not= e$$):

$$f$$ by definition must be injective, injective basically means that $$f$$ doesn't map different elements in the domain $$(\mathbb{N})$$ to the same element in the range/codomain $$(\mathbb{N})$$. Say you had a function $$g$$ s.t. $$g(1)=1$$ and $$g(2)=1$$, that cannot happen if $$g$$ is injective because $$g$$ doesn't map different elements $$(1\not=2)$$ to the same element $$(\text{in this case } 1)$$.

As mentioned by hellofriends in the comments:

Suppose $$f(m)=f(n)$$ then $$f(m)+f(m)=f(n)+f(m)$$ and applying $$f$$ to both sides $$f(f(m)+f(m))=f(f(n)+f(m))$$ $$m+m=n+m$$ $$m=n$$ after subtracting $$m$$ from both sides, thus if $$f(m)=f(n)$$ then $$m=n$$ and $$f$$ must be injective.

By definition of a function every input must have an output, thus $$1$$ must be mapped to something, call it $$s\in \mathbb{N}$$. We can assume $$s \not= 1$$ because then $$f(n)=n\:$$ $$\forall n \in \mathbb{N}$$ which clearly satisfies $$f(f(m)+f(n))=f(m+n)=m+n$$, and we can assume that $$s\not= 2$$ because then $$f$$ would not be injective or well-defined, $$1\mapsto 2$$ then $$4 \mapsto 2$$ and then $$2+2 = 4 \mapsto 1+4 =5$$. Let $$\alpha \geq 0$$.

Given $$\color{blue}{(1)}1 \mapsto s$$, then $$\color{blue}{(2)}2s \mapsto 2$$ and $$4 \mapsto 4s$$, from then on we can use $$\color{blue}{(1)},\color{blue}{(2)}$$ consecutively to get $$5s\mapsto 5, 8s \mapsto 8,..., (3\alpha + 2)s \mapsto (3\alpha + 2),...$$ thus we have $$f$$ must be surjective onto $$[2]_3 \cap \mathbb{N}$$.

Also $$2$$ must be mapped to something, $$s' \in \mathbb{N}$$ where $$s' \not= s$$ because $$f$$ is injective. $$s’ \not= 1$$ because then $$2\mapsto 1$$ implies $$2 \mapsto 4$$ and $$f$$ would not be well-defined.

Then $$2 \mapsto s'$$ and using $$\color{blue}{(1)}$$ we get $$s+s'\mapsto 3$$, then $$\color{blue}{(1)},\color{blue}{(2)}$$ consecutively $$4s + s' \mapsto 6, 7s + s' \mapsto 9, 10s+s'\mapsto 12,...,(3\alpha +1)s+s'\mapsto 3\alpha +3,...$$ consequently $$f$$ must be surjective onto $$[0]_3 \cap \mathbb{N}$$.

Also since $$2 \mapsto s'$$, $$2s' \mapsto 4$$ and using $$\color{blue}{(1)},\color{blue}{(2)}$$ consecutively $$3s + 2s' \mapsto 7, 6s+2s'\mapsto 10,..., 3\alpha s+2s'\mapsto 3(\alpha +1)+1$$ and thus $$f$$ must be surjective onto $$[1]_3\cap \mathbb{N} \setminus \{1\}$$.

$$f$$ is pretty close to surjective, all that's missing is the existence of $$\gamma \in \mathbb{N}$$ s.t. $$f(\gamma)=1$$.

edit:

Thanks to Carl’s proof it looks like my post was half-baked, I started by letting $$1\mapsto 2$$ and derived a contradiction, I should of kept going and tried other values because it turns out that as you try other values for $$f(1)>1$$ they all somehow lead to a contradiction and the above arguments can be used to demonstrate this:

Suppose $$1\mapsto (3\alpha +2) \in [2]_3 \cap \mathbb{N}$$ then $$(3\alpha+2)^2 \mapsto 3\alpha +2$$ and $$(3\alpha+2)^2 \geq 4 >1$$. $$f$$ would not be injective, contradiction.

Suppose $$1\mapsto 3\alpha +3 \in [0]_3 \cap \mathbb{N}$$ then $$(3\alpha +1)(3\alpha +3)+s’ \mapsto 3\alpha +3$$ and $$(3\alpha+1)(3\alpha+3)+s’\geq 3+s’>3>1$$ because $$s’>0$$. $$f$$ would not be injective, contradiction.

Suppose $$1\mapsto 3(\alpha +1)+1 \in [1]_3 \cap \mathbb{N}$$ then $$3\alpha(3(\alpha +1)+1)+2s’ \mapsto 3(\alpha +1)+1$$ and $$3\alpha(3(\alpha +1)+1)+2s’\geq 0+2s’ \geq 2\cdot 1 >1$$. $$f$$ would not be injective, contradiction.

Since we ran through all possiblities $$1\mapsto s \in \mathbb{N}\setminus\{1\}$$ and they all led to a contradiction, one way or another, we are left only with the original case we knew that worked $$1 \mapsto 1$$, i.e. $$f$$ is the identity.