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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

My solution:

As it is already shown by @Carl Schildkraut that $f$ is one-one.

Let $k<n$, then from $f(f(m)+f(n))=m+n \cdots(1)$

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

Using the fact $f$ is one-one functions, this implies $f(m+k)+f(n-k)=f(m)+f(n)\; \forall \; m,n,k\in \mathbb N\;, k<\mathbb N\cdots(2)$

Suppose, $f(1)=b>1$. Then $b$ is at least 2.

Moreover We get

$f(2b)=f(f(1)+f(1))=2\;$ and $\; f(b+2)=f(f(1)+f(2b))=1+2b \cdots (3)$.

But $b$ cannot be $2$ because if it is $2$ the above equation $(3)$ gives contradictory result.

Now using Equation $2$

$f(2b)+f(1)=f(2b-(b-2))+f(1+(b-2))=f(b+2)+f(b-1)$.

$\implies$

$2+b=1+2b+f(b-1)$

$\implies$

$f(b-1)=1-b$. But this is impossible since $1-b<0$ and $f(1-b)\geq 1$ Now we conclude that $b=1$.

Thus $2=f(2b)=f(2)$.

Now we compute the proof by induction. Suppose $f(k)=k$ $\forall \; k\leq n\;$.

Using the given equation we obtain $n+1=f(f(n)+f(1))=f(n+1)$

Since $f(n)=n$ by induction hypothesis. It follows that $f(n)=n \;\forall \in \mathbb N$