The functional equation $f\bigl(m+f(n)\bigr)=f\bigl(f(m)\bigr)+f(n)$ - Understading an easy step in my solution.

Question

I am trying to solve the equation and find all $f: \mathbb{N} \rightarrow \mathbb{N}$ such that: $$f\bigl(m+f(n)\bigr)=f\bigl(f(m)\bigr)+f(n)$$ for all $n, m \in \mathbb{N_{0}} $.

A reasonable approach to begin with would be to determine some special values of $f$. If we let $m=n=0$, we get $$f\bigl(f(0)\bigr)=f\bigl(f(0)\bigr)+f(0)$$ which I intuitively would say implies $f(0)=0$. But is that really true? How do I prove it? I got the intuition from solving equal problems to this one but I haven't yet ascertained whether it's true or not. It fells like an easy step but I'm having a brain-fog here.

Answer 1

Comments already showed that :

• $f(0)=0$
• $f$ injective or $f$ surjective $\Rightarrow f = \text{id}$
• $f|_I = \text{id}$ on $I=\text{Im}(f)$
• $I=\text{Im}(f)$ is stable by $+$ ; in particular, if $x \in I$ and $k \in \mathbb{N}$, $f(kx)=kf(x)$
• $f=0$ is a trivial solution ; we assume $I^* = I - \{0\} \neq \emptyset$ hereafter

Let's note $a=\min I^*$.

If $a=1$, $f=\text{id}$ since we'd have $\forall m, f(m+f(1))=f(m+1)=f(f(m))+f(1)=f(m)+1$.

Let's assume $a > 1$. By definition, no element of the integer interval $[1, a-1]$ is in $I$.

We already know that $a\mathbb{N} \subset I$. If $u \not\in I$, it's easy to see that $a+u \not\in I$ (since $f(a+u)=f(u+f(a))=f(u)+a\not=u+a$). Therefore, $[1, a-1]$ and all its translations by multiples of $a$ have no common element with $I$.

Conclusion: $I = \text{Im}(f) = a\mathbb{N}$ and $\forall n\in\mathbb{N}$, $\exists g(n) \in \mathbb{N}$ s.t. $f(n)=g(n)a$. And we already know that $\forall k, g(ka)=k$.

Substituting $f$ by $ag$ and $n$ by $a$ in the problem's equality, we obtain $g(m+a)=g(m)+1$. With an easy induction and noting $n\%a$ the remainder of $n$ divided by $a$, we get : $$\forall n, g(n) = \lfloor n/a \rfloor + g(n\%a)\;\;\;\;\;(X)$$ Basically, this means that $g$ takes certain values on $[0, a-1]$ (among which $g(0)=0$) and for every translation (to the right) of the input interval by $a$, $g$ translates (upwards) the image values by $1$.

Reciprocally, let's take an integer $a \ge 2$ and $g : \mathbb N \rightarrow \mathbb N$ that verifies $g(0)=0$ and uniquely determined by its restriction to $[1, a-1]$ by equation $(X)$. We easily see that $g(a)=g(0)+1 = 1$ and $\forall m,k, g(m+ka)=g(m)+k$.

Let's also define $f : n \mapsto ag(n)$ and take $m,n$ two integers. Then $f(m+f(n))=ag(m+ag(n))=a(g(m)+g(n))=f(m)+f(n)$ and $f(f(m))=ag(ag(m))=ag(m)=f(m)$, in short: $$f(m+f(n))=f(f(m))+f(n)\;\;\;\;\;(Y)$$

This proves that the solutions $f$ of the functional equation are exactly the functions $f=ag$ of the form we just described.

Example: with $a=2$ and $g(1)=3$, $f(n) = n$ if $n$ is even, and $f(n)=n+5$ if $n$ is odd. Testing all odd/even combinations of a couple of integers $(m,n)$ quickly shows that $f$ satisfies $(Y)$.

QED

Answer 2

Here I have a partial solution for your functional equation $$f(m+f(n))=f(f(m))+f(n)$$ you have prove that $f(0)=0.$ (your proof is correct.)
Set of fixed point set of $f$ is non empty (because $0$ is a fixed point).
Suppose $n_0$ is a fixed point of $f$ then we have $f(n_0+f(n_0))=f(2n_0)=2f(n_0)=2n_0.$
By mathematical induction we can show that $$f(kn_0)=kn_0, \forall k \in N.$$ This means $kn_0$ is also a fixed point of this function $f$ for any integer $k.$

Note that $f(f(0))=f(0)=0$ and $$f(n)=0, \forall n\in N$$ is a solution for this functional equation.
Put $m=0$ in to original equation, then we have $f(f(n))=f(n).$
Suppose $f$ is a $1-1$ map, then $$f(n)=n ,\forall n\in N$$ Also we have $$f(m+f(n))=f(m)+f(n)$$ $$f(m+f(n))=f(n+f(m))$$

When $f$ not a $1-1$ map............................

This seems like, I also need some more sleep too.