1
$\begingroup$

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.

$\endgroup$
9
  • 5
    $\begingroup$ Does ${\mathbb N}$ contain $0$? $\endgroup$
    – Yuval
    Feb 25 at 3:50
  • $\begingroup$ Have you found a candidate function? What did you learn from plugging in values? Did you determine any? $\endgroup$ Feb 25 at 4:13
  • $\begingroup$ What is a candidate function? also I di not get any by plugging in values. I was not able to determine any value $\endgroup$
    – Shashaank
    Feb 25 at 4:16
  • $\begingroup$ Can you think of some easy examples of $f$ that satisfy the equation, for example constant/linear ones? $\endgroup$ Feb 25 at 4:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – C Squared
    Feb 25 at 10:38
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.