Find $f: \mathbb{N_0} \to \mathbb{N_0}$ which satisfies $f^n(x+f(y))=f^{n+1}(x)+f^n(y) \text{ for } n \in \mathbb{N}.$

functional-equations

Find $f: \mathbb{N}_0 \to \mathbb{N}_0$ which satisfies
$$f^n(x+f(y))=f^{n+1}(x)+f^n(y) \quad \text{ for a given } n \in \mathbb{N}.$$
($f^n$ means $\underbrace{f \circ f \circ f \circ \cdots \circ f}_{\times n}$.)

My Attempt:

\begin{align}
P(0, 0): \; & f^{n+1}(0)=f^{n+1}(0)+f^n(0). \\
\therefore \; & f^n(0)=0. \\
\ \\
P(x, f^{n-1}(0)): \; & f^{n}(x)=f^{n+1}(x)+f^{n-1}(0). \\
P(0, y): \; & f^{n+1}(y)=f(0)+f^n(y). \\
P(0, f^{n-1}(0)): \; & -f^{n-1}(0)=f(0). \\
\ \\
&\text{let } \mathbb{F^n}=\{ f^n(x) | x \in \mathbb{N_0}. \} \Rightarrow 0 \in \mathbb{F^n}. \\
\Rightarrow \; &\text{For } \forall x_n \in \mathbb{F^n}, \ \boxed{f(x_n)=x_n+c.} \\
c \; & =-f^{n-1}(0) \leq 0. \\
c \; & = f(0) \geq 0. \\
\ \\
\therefore \; & c=0, f(x_n)=x_n \text{ for } \forall x_n \in \mathbb{F^n}. \\
\ \\
\therefore \; & f^n(x+f(y))=f^n(x)+f^n(y). \\
& f^n(y+f(x))=f^n(x)+f^n(y).
\end{align}

Now, what I would like to show is that $\mathbb{F^n} = k\mathbb{N_0}$.

Best Answer

Answer: any function satisfying this equation is

  • either $f^n(x) = 0$ for any $x$ (there is much freedom in the construction of such an $f$);
  • or there exists $k > 0$ and nonnegative integers $a_0 = 0, a_1, \dots, a_{k - 1}$ such that $f(r + qk) = (a_r + q)k$ for all $q \geq 0$ and all $0 \leq r < k$.

One can easily verify that any $f$ of the above forms satisfy the original functional equation.

Let us show that there is no other solution. Suppose that $f$ satisfies the functional equation and $f^n$ is not constantly zero.

We continue from the result of the OP that $f(0) = 0$ and $f^n(x) = f^{n + 1}(x)$ for all $x$.

Write $F = f^n$, so that the original equation becomes $F(x + f(y)) = F(x) + F(y)$.

Using this equation, it is easy to show by induction on $m$ that $$F(x + mf(y)) = F(x) + mF(y)\tag 1$$ for any $m \in \Bbb N_0$.

Setting $x = 0$ and $m = f(z)$ in $(1)$ gives $F(f(z)f(y)) = f(z)F(y)$ for any $y, z$.

Exchanging $y, z$ in the above equation, we get $f(z)F(y) = f(y)F(z)$ for any $y, z$.

By our assumption, there exists $t$ such that $F(t) \neq 0$. Setting $z = F(t)$ in the above equation gives $f(y) = F(y)$ for any $y$, i.e. $f = F$.

Now let $k$ be the smallest nonzero element in the image of $f$ (which is the same as the image of $F$). We have $f(k) = k$ and thus setting $y = k$ in equation $(1)$ gives us $$f(x + mk) = f(x) + mk\tag 2$$ for any $x, m$.

Let us show that $k \mid f(x)$ for any $x$. Write $f(x) = ka + b$ with $0 \leq b < k$. Setting $x = b$ and $m = a$ in $(2)$, we get $f(f(x)) = f(b) + ka$. But $f(f(x)) = f(x)$, hence we get $f(b) = b$, namely $b$ lies in the image of $f$. However, $b$ is strictly smaller than $k$, which is by construction the smallest nonzero element in the image of $f$. This means that $b = 0$ and $f(x) = ka$ is a multiple of $k$.

Therefore for each $i = 0, 1, \cdots, k - 1$ we can write $f(i) = a_ik$ (with $a_0 = 0$) and the function $f$ is totally determined by those $a_i$ and the equation $(2)$.

Related Question