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

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