Let $P(x,y,z)$ denote the assertion $$f^{f^{f(x)}(y)}(z)=x+y+z+1$$. Notice that $P(x,y,f(z))$ implies $$f^{f^{f(x)}(y)}(f(z))=x+y+f(z)+1$$but also $$f^{f^{f(x)}(y)}(f(z))=f(f^{f^{f(x)}(y)}(z))=f(x+y+z+1)$$So we can deduce that $$f(x+y+z+1)=x+y+f(z)+1$$Now notice that we can write every natural number $\geq 3$ as $x+y+1$ for $x,y \in \mathbb{N}$ so we get that $f(k+z)=f(z)+k $ $\forall k \in \mathbb{N}$ such that $k \geq 3$. Now notice that by this we get that \begin{align*} & f(z+4)=f(z)+4 \\ & f(z+4)=f(z+1)+3 \\ \end{align*}And so we get that $$f(z+1)=f(z)+1 \forall z \in \mathbb{N}$$and this implies that $$f(z)=z+f(1)-1 \forall z \in \mathbb{N}$$Let $f(1)-1=c$. Substituing this in the original assertion yields that \begin{align*} & f^{f^{f(x)}(y)}(z) \\ & =f^{f^{x+c}(y)}(z) \\ &=f^{y+c\cdot (x+c)}(z) \\ &=z+(y+c \cdot (x+c))\cdot c \\ &=z+cy+c^2x+c^3 \\ \end{align*}Notice that clearly if $c>1$ then $z+cy+c^2x+c^3 > x+y+z+1$ which is a contradicition so $c=1$ and we get that $f(x)=x+1 \forall x \in \mathbb{N}$ which clearly works.

Let $P(x,y,z) : f^{f^{f(x)}(y)}(z) = x+y+z+1 \ \forall \ x,y,z \in \mathbb{N} $ We will show that $f(x) = x+1 \ \forall \ x \in \mathbb{N} $ Claim : $f$ is injective Let $ f(z) = f(w) $ let $ k = f^{f(x)}(y) $ Then $ f^k(z) = f^k(w) \Rightarrow z = w $. Claim : $f(x) > 1 \ \forall \ x \in \mathbb{N} $ Suppose on the contrary $\exists \ a \in \mathbb{N} $ such that $ f(a) = 1 $ Plugging $P(1,1,1)$ gives $ 3a=0 $(Contradiction). Lemma : Let $a,b \in \mathbb{N} $ such that $f^a(x) = f^b( x) \ \forall \ x \in \mathbb{N} $ then $ a=b $. Suppose $ a > b $ and let $ c = a-b$ Now as $f$ is injective we get $ f^c(x) = x \ \forall \ x \in \mathbb{N} $ Then we get $ f $ is surjective but we have already shown that $ \not \exists \ a \in \mathbb{N} $ such that $f(a) = 1$ ( Contradiction ). Hence $ a=b $. Now $ f^{f^{f(x)}(y)}(z) = x+y+z+1 = f^{f^{f(y)}(x)}(z) $ Now using our lemma we get $\boxed{ f^{f(x)}(y) = f^{f(y)}(x) \ \forall \ x,y \in \mathbb{N} }$ Let $ k = f^{f(y) - 1 }( z) $ Then $f^{f(x) + f(y) - 1 }(z) = f^{f(x)} (k) = f^{f(k)} (x) = f^{ f^{ f(y) }(z) } (x) = f^{ f^{f(y)}(x)}(z) $ And again using our lemma we deduce that $ \boxed{f^{f(y)}(x) = f(x)+f(y)-1 \ \forall \ x,y \in \mathbb{N} }$ Let $ f(1) = c $ Then $ P(1,1,z) : f^{2c-1}(z) = z+3 \ \forall \ z \in \mathbb{N} $ And $ f^c(x) = f(x) + c - 1 $ Plugging $ x = f^{c-1}(z) $ we get $ f^{2c-1}(z) = f^c(z) + c-1 $ $ \Rightarrow f(z) = z + 5 - 2c $, plugging $z=1$ we get $ c=2 $ and hence $\boxed{ f(z) = z+1 \ \forall \ z \in \mathbb{N }} $ Which indeed is the only solution.

Claim 1: The function $f$ is injective. Proof: Suppose $f(x)=f(y)$. Then $f^{f^{f(x)}(x)}(x)=f^{f^{f(y)}(y)}(y)$, or $3x+1=3y+1$ implying that $x=y$. $\square$ Claim 2: Let $\text{ran}(f)$ denote the range of $f$. Then $1\not\in \text{ran}(f)$. Proof: Suppose otherwise that $f(x)=1$. Then $f^{f^{f(x)}(x)}(x)=f^{f(x)}(x)=f(x)=1=3x+1$ which gives $x=0$, contradiction. $\square$ Claim 3: Let $u,v,x,y\in\mathbb{N}$ such that $u+v=x+y=k$ (say). Then $f^{f(x)}(y)=f^{f(u)}(v)$. Proof: Fix some $z\in\mathbb{N}$. Then $f^{f^{x}(y)}(z)=x+y+z+1=u+v+z+1=f^{f^{u}(v)}(z)$. Let $m=f^{f(x)}(y)$ and $n=f^{f(u)}(v)$. WLOG $m\geq n$. Then $f^{m-n}(z)=z$. Also $f^n(z)=z+k+1$. Note that for any $l\in \mathbb{N}$, we have $f^{l(m-n)}(z)=f^{m-n}(z)=z$ and $f^{ln}(z)=z+l(k+1)$. Thus $f^{n(m-n)}(z)=z=z+(m-n)(k+1)$ which is only possible if $m=n$. $\square$ Claim 4: The minimum element of $\text{ran}(f)$ is $f(1)$. Proof: Suppose that the minimum element is $f(k)$. If $k\neq 1$, then by Claim 3, we have $f^{f(1)}(k)=f^{f(k)}(1)$, so $f^{f(1)-f(k)}(k)=1$ implying that $1\in\text{ran}(f)$, which is false by Claim 2. So we can conclude that $k=1$. $\square$ Claim 5: The range of $f$ is $\{2,3,4,\dots \}$. Proof: We already know that $1$ is not in the range. Now for any other $x\in \mathbb{N}$ we have $f(x)>f(1)$, so $f^{f(x)}(1)=f^{f(1)}(x)$ or $f^{f(x)-f(1)}(1)=x$ and so $x\in\text{ran}(f)$. $\square$ (As a direct corollary, we have $f(1)=2$) Claim 6: For all $n\in\mathbb{N}$, we have $f^n(1)=f(1)+n-1=n+1$. Proof: Note that for all $a,b\in \mathbb{N}$, we have $f^{f^{f(a)}(b)}(1)=f^{f^{f(a)}(1)}(b)=a+b+2$. If $b\neq 1$, then $f^{f(a)}(b)\neq f^{f(a)}(1)$. If $f^{f(a)}(b)< f^{f(a)}(1)$, then we'll get $f^{f^{f(a)}(1)- f^{f(a)}(b)}(b)=1$ which cannot be possible. So $f^{f(a)}(b)> f^{f(a)}(1)$ for all $a,b\in \mathbb{N}$. Choosing $b=2=f(1)$, we get $f^{f(a)}(f(1))=f^{f(a)+1}(1)>f^{f(a)}(1)$. Since this holds for all $a\in\mathbb{N}$, and since $f(a)\geq 2$, it follows that $f(1)<f^2(1)<f^3(1)<\dots$ and so on. Now note that every $x\in \{2,3,4,\dots\}$ can be written as $f^m(1)=x$ where $m=f(x)-f(1)$. Also if $k\neq l$, then $f^{k}(1)\neq f^l(1)$ because otherwise $1\in\text{ran}(f)$. Thus each $x$ can be uniquely written as $f^m(1)=x$. All this implies that $\{f(1),f^2(1), f^3(1),\dots\}=\{2,3,4,\dots\}$, and the monotonicity of $f^k(1)$ gives us $f(1)=2$, $f^2(1)=3$, $f^3(1)=4$ and generally $f^k(1)=f(1)+k-1=2+k-1=k+1$. $\square$ The Conclusion: Now from Claim 6, for all $k>1$, we have $k+1=f^k(1)=f(f^{k-1}(1))=f(k-1+1)=f(k).$ Combining this with $f(1)=2$, we get that $f(x)=x+1$ for all $x\in\mathbb{N}$. We can verify that this function works. Hence $\boxed{f(x)=x+1}$ is the only solution. $\blacksquare$

Solution: Let $P(x,y,z)$ denote the assertion that $f^{f^{f(x)}(y)}(z) = x+y+z+1$ $\textcolor{blue}{Claim1:}$There does not exists a $a\in \mathbb N$ such that $f(a)=1$. $\textcolor{red}{Proof:}$ FTSOC, assume there exists such $a\in \mathbb N$ such that $f(a)=1$.Then $P(a,a,a)$ gives: $f^{f^{f(a)}(a)}(a) =a+a+a+1=3a+1$ or,$f^{f(a)}(a) =3a+1$ or,$f(a)=3a+1$ or,$1=3a+1$ or,$a=0$.Contradiction. Hence, There is no $a\in\mathbb N$ such that $f(a)=1$ $\square$. $\textcolor{blue}{Claim2:}$$f$ is an one to one function. $\textcolor{red}{Proof:}$ By Claim1, it is clear that $f^{f(x)}(y)>1$. Let for some $m,n\in\mathbb N$ we have $f(m)=f(n)$. Then,$f^{f^{f(x)}(y)-1}(f(m))=f^{f^{f(x)}(y)-1}f(n)$ or,$f^{f^{f(x)}(y)}(m)=f^{f^{f(x)}(y)}(n)$. or,$x+y+m+1=x+y+n+1$ or,$m=n$ Hence, $f$ is one to one function.$\square$ $\textcolor{blue}{Claim3:}$ $f$ is increasing on $\mathbb N$ $\textcolor{blue}{LEMMA:}$ Suppose for some $a,b\in\mathbb N$ we have $f^a(1)=f^b(1)$.Then we have $a=b$ $\textcolor{red}{Proof:}$ FTSOC, Assume there exists $a,b\in\mathbb N$ such that $a>b$ and $f^a(1)=f^b(1)$.For injectiveness of $f$ we have $f^{a-1}(1)=f^{b-1}(1)$.Running same way we will get $f^{a-b}(1)=1$.As $a-b$ is positive, this contradicts Claim1.Hence $a=b$$\square$. Now,for $x\in\mathbb N$ and $2\le y\in \mathbb N$,$P(x+1,y-1,1)$ and $P(x,y,1)$ gives: $f^{f^{f(x+1)}(y-1)}(1) = x+1+y-1+1+1 =x+y+1+1 =f^{f^{f(x)}(y)}(1) $ So $f^{f^{f(x+1)}(y-1)}(z) =f^{f^{f(x)}(y)}(1) = x+y+z+1$ Using the Lemma we can derive, $f^{f(x+1)}(y-1)=f^{f(x)}(y)$ for all $x\in\mathbb N$ and for all $2\le y\in\mathbb N$ Put $y=2$ in the last equation. We have $\boxed{f^{f(x+1)}(1)=f^{f(x)}(2)}$. Now, if $f(x)>f(x+1)$ for some $x\in\mathbb N$ then using injectivity of $f$,we have $f^{f(x)-f(x+1)}(2)=1$.$f(x)-f(x+1)$ is positive by our assumption.Hence $f(stuff)=1$ contradicting Claim1. Now by injectivity $f(x)$ can't be equal to $f(x+1)$.Hence, $f(x+1)>f(x)$ for all $x$.$\square$ $\textcolor{blue}{Claim4:}$ $f$ is linear. $\textcolor{red}{Proof:}$ Let $g(x)=f(x+1)-f(x)$.By above claim $g(x)$ is positive integer for all $x$ Now in the proof of Claim3 we have found that $f^{f(x+1)}(1)=f^{f(x)}(2)$. Using injectivity of $f$ we have $f^{f(x+1)-1}(1)=f^{f(x)-1}(2)$.Running in the same manner we get $\boxed{f^{f(x+1)-f(x)}(1)=2}$ or,$f^{g(x)}(1)=2$.for all $x\in\mathbb N$ Now take any two natural number $a,b$. we have$f^{g(a)}(1)=2=f^{g(b)}(1)$.Using the lemma we get $g(a)=g(b)$. So $g(x)=f(x+1)-f(x)$ is a constant function.Now as $f$ is a function from $\mathbb N\to\mathbb N$ so $f$ is a linear function.Assume $f(x)=ax+b$.$\square$ $\textcolor{blue}{Claim5:}$$a=b=1$ or $f(x)=x+1$. $\textcolor{red}{Proof:}$ As $f$ is increasing and can't take 1 so $f(1)>1$.As $f$ is increasing so $f(f(1))>f(1)$.By induction we have $f^{n+1}(1)>f^n(1)$ for all positive integer $n$ . Now,as $f^{f(x+1)-f(x)}(1)=2$ and $g(x)=f(x+1)-f(x)=c>0$ is a constant so we claim that c=1.If not assume $c>1$.Or,$c-1>0$ $f^{f(x+1)-f(x)}(1)=f^c(1)=2$ or,$f(f^{c-1}(1)=2$.But $f^{c-1}(1)\ge 2$ as $c-1>0$.Or $f^c(1)>2$ Using increasingness. A contradiction. So $c=f(x+1)-f(x)=1$. $f^c(1)=f(1)=2$. So $f(2)-f(1)=1or, f(2)=3$ By induction $\boxed{f(x)=x+1}$ for all $x\in\mathbb N$.Plugging it in the main equation we get, it is indeed a solution. $\blacksquare$

The answer if $f(x)=x+1$. It is trivial to verify that this works. Now we prove this is the only one. Let $P(x,y,z)$ denote the assertion $$f^{f^{f(x)}(y)}(z)=x+y+z+1$$$P(x,y,f(z))$ gives $$f^{f^{f(x)}(y)}(f(z))=x+y+f(z)+1$$and $$f^{f^{f(x)}(y)}(f(z))=f(f^{f^{f(x)}(y)}(z))=f(x+y+z+1)$$which implies $$x+y+1+f(z)=f(x+y+z+1)$$Letting $z=1$, this gives that $$f(x+y+2)=f(1)+x+y+1$$so for all $x\geq 4$, we get $$f(x)=f(1)+x-1$$Let $f(1)=a$, so that for all $x\geq 4$, $$f(x)=x+(a-1)$$Note $f(1)=a$ must be a positive integer, so $f(x)=x+(a-1)\geq x$ and it follows by induction that $$f^m(x)=x+M(a-1)$$Now, $P(4,4,4)$ gives $$f^{f^{f(4)}(4)}(4)=13$$$$\Rightarrow f^{f^{a+3}(4)}(4)=f^{4+(a+3)(a-1)}(4)=f^{a^2+2a+1}(4)=4+(a-1)(a^2+2a+1)=13$$$$\Rightarrow a^3+a^2-a-10=0$$which factors as $$(a-2)(a^2+3a+5)=0$$so we see that this means $f(1)=a=2$, and $f(x)=x+1$ for $x\geq 4$ Now, from $f(x+y+z+1)=f(z)+x+y+1$, $$f(1+1+2+1)=f(2)+1+1+1 \Rightarrow 6=f(2)+3 \Rightarrow f(2)=3$$and $f(1+1+3+1)=f(3)+1+1+1 \Rightarrow 7=f(3)+3 \Rightarrow f(3)=4$. Therefore we get that $f(x)=x+1$ for all positive integers $x$. We know that this works, so we are done.

Wrong

ghu2024 wrote: Let $f\left(x\right)$ be a polynomial in form $a_nx^n+a_{n-1}x^{n-1}+\ldots+a_2x^2+a_1x+a_0$ You cannot assume that $f$ is a polynomial.

Claim: The only solutions are $f(x)=x+1$. We can verify that works as shown. $$f^{f^{f(x)}(y)}(z)=f^{f^{x+1}(y)}(z)=f^{x+y+1}(z)=x+y+z+1.$$Let $P(x,y,z)$ be the assertion. Let $w$ be an integer. $P(w,x,y) \implies f^{f^{f(w)}(x)}(y)=w+x+y+1.$ $P(f^{f(w)-1}(x),y,z) \implies f^{f^{f^{f(w)}(x)}(y)}(z)=f^{w+x+y+1}(z)=f^{f(w)-1}(x)+y+z+1. \qquad \qquad(1)$ Let the assertion of $(1)$ be $Q(w,x,y,z)$. $Q(w,x,1,z) \implies f^{w+x+2}(z)=f^{f(w)-1}(x)+z+2.$ $Q(w,x,2,z) \implies f^{w+x+3}(z)=f^{w+x+2}(f(z))=f^{f(w)-1}(x)+f(z)+2=f^{f(w)-1}(x)+z+3 \implies f(z)=z+1.$ This means the only solutions are $\boxed{f(x)=x+1}$.

$f$ is injective by plugging in two different $x's$ and surjective onto $\mathbb N+3 $ (integers $> 3$). Note that, $x+y+z+1 = f^{f^{f (x)(y)}}(z),$ so in other words, every integer greater or equal to $z+3$ can be reached from $z$ by applying $f$ enough times. Since this set is infinite, $f$ is aperiodic. $f^n$ has no fixed points for any $n.$ It follows that if $f(s)=t,$ then the set of integers reachable from $t$ contains those reachable from $s.$ We know $\mathbb N+3$ is in the image of $f$ we can prove this putting $z=n,x=y=1$ $f(x)\le x-2$ by aperiodicity $f(x)=\setminus=x$ $f$ is injective. To prove injectivity note that because $f^{f^{f(x_1)(y)}}(z) =\setminus= f^{f^{f(x_2)(y)}}(z)\implies f(x_1)=\setminus=f(x_2).$ Now, call $\{x,f(x),f^2(x),\hdots\}$ the orbit of $x,\mathcal{O}(x),$ and call the position of $x= \left|\frac{\mathbb N}{\mathcal {O}(x)}\right|,$ the natural numbers we can't reach from $x.$ Then the position of $n$ is at most $n+1. $ Since all of $n,n+3,n+4\hdots$ are in its orbit. The position of $f(n)$ is always one more than the position of $n.$ Since we can reach all the same numbers except $n.$ If we put $x=y=z=1,$ I get that since the position of $4$ is at most $5,f^{f(1)}(1)$ is at most $5. $ Since the position of $5$ is at most $6$ then $f(1)\le 6. $ If we just put $y=z=1,$ similarly $f(x)\le x+5. $ If $f(1)=6,$ then $4$ is position $5$ and $5$ is position $6. $ Whereas $6$ is position $1,$ which doesn't work because $f$ can't go down by more than $2.$ If $y$ is in the orbit of $x,$ by acyclicity $x$ is not in the orbit of $y.$ So the position of n is at least $n-3,$ as $n $ is always in the orbit of any number at most $n-3.$ Hence, $n-3\le\mathrm{pos}(n)\le n+1. $ The number with position $1$ is at most $3,$ and the start of the chain can be only $1$ or $2\to 1$ or $2\to 3\to 1$ or $3\to 1$ or $3\to 2\to 1.$ $2\to 3\to 1$ and $3\to 2\to 1$ are impossible, because $f(1)\ge 4,f^{f(1)}(1)\ge 4, f^{f^{f(1)(1)}}(1)$ has position at least $6,$ and for $x=y=z=1$ we have $x+y+z+1=4,$ which has position at most $5.$ If $f(t)=1$ Substituting $x=y=z=t$ yields $1=3t+1,$ so $1$ is in position $0.$ If $f(1)<6$ If $1\to 5,$ since $\mathrm{pos}(2)\le 3, $ either $1\to 5\to 4\to 2$ or $1\to 5\to 3\to 2.$ First case contradicts $x=4,y=5,z=1; $ second case contradicts $x=3,y=5,z=1.$ Thus $f(1)<5.$ If $f(1)=\setminus=2$ Then there is a $t$ with $f(f(t))=2,$ so put $x=f(t), y=t, z=t$ to get $2t+f(t)+1=2,$ so $f(1)=2.$ Similarly, if $f(2)=\setminus=3$ Put $f(f(f(t)))=3,$ then $x=f(f(t)), y=z=t\implies 2t+f(f(t))+1=3.$ Hence $f(2)=3.$ The same trick works for $4.$ We get $2t+f(f(t))+1=4,$ which is possible only if $t=f(f(t))=1,$ which is false. So $f(1)=2, f(2)=3, f(3)=4,$ and from here we can get $f(n)=n+1$ just by substituting $x=y=1, z=n-2.$

I claim the only solution if $f(x)=x+1$, which is easily verified. Let $P(x,y,z)$ denote the given assertion. Claim: $f$ is injective Suppose $f(a)=f(b)$ for some $a\ne b$. Taking $P(a,1,1)$ and $P(b,1,1,)$ give \[a+3=f^{f^{f(a)}(1)}(1)=f^{f^{f(b)}(1)}(1)=b+3\]so $a=b$, meaning $f$ is injective. A consequence of this is now that for $m\geq n$, and if $f^m(c)=f^n(d)$ for some $c,d$, then $f^{a-b}(c)=d$ (by "unwrapping" $f$ multiple times). Now take $P(x,y,z)$ and $P(y,x,z)$. Since swapping $x$ and $y$ leaves $x+y+z+1$ unchanged, these two quantities are equal. Unwrapping the $f$ then gives \[f^{f^{f(x)}(y)}(z)=f^{f^{f(y)}(x)}(z)\implies f^{|f^{f(x)}(y)-f^{f(y)}(x)|}(z)=z\] Claim: $f^{f(y)}(x)=f^{f(x)}(y)$ Suppose there exist $x$ and $y$ such that the quantities are not equal, and let their absolute difference be $p$. This means that $f^p(z)=z$, or $f$ has period of $p$. Consider taking $P(f^{p-1}(p), p, p)$: \[P(f^{p-1}(p),p,p)=f^{f^{f^p(p)}(p)}(p)=f^{f^p(p)}(p)=f^p(p)=f^{p-1}(p)+p+p+1\]\[\implies p=f^{p-1}(p)+2p-1\implies f^{p-1}(p)+p=1\]which is a contradiction since $p$ and $f^{p-1}(p)$ are positive integers. Thus $f$ is not periodic and $f^{f(y)}(x)=f^{f(x)}(y)$ for all $x$ and $y$. The finish from here is easy. Note that $f$ can take on any value greater than or equal to $1+1+1+1=4$ by the given condition with suitable choices of $x,y,z$. Claim: $f(x)=x+1$ for $x\geq 4$. For some $n\geq 4$, consider $a$ and $b$ such that $f(a)=n$ and $f(b)=n+1$ (which exist since $f$ is "surjective" from $4$ to infinity). Using the previous claim, \[f^{f(a)}(b)=f^{f(b)}(a)\implies f^n(b)=f^{n+1}(a)\implies f^{n-1}(n+1)=f^n(n)\implies f(n)=n+1\]as claimed. Claim: $f(x)=x+1$ for $x\leq 3$. Simply take $P(x,4,4)$: \[f^{f^{f(x)}(4)}(4)=f^{4+f(x)}(4)=8+f(x)=x+4+4+1\implies f(x)=x+1\] Combining the previous two claims gives $f(x)=x+1$ for all positive integers $x$, as advertised.

Wacko I got a 5 on this question (-1 for not showing "$f(x)=x+1$ easily works" and -1 for something else i forgot.) but just do $f(z+(y+2))=f^{N+1}(z+(y+2))=f(z)+(y+2)$ where $N$ is the thing up top. Motivation comes from triple involution trick ;-;

We claim $f(x)=x+1$ for all $x$. It is easy to see that this works: \[ f^{f^{f(x)}(y)}(z) = z+f^{f(x)}(y)=z+y+f(x)=z+y+x+1, \]as desired. Call the statement $P(x,y,z)$. Taking $f$ of $P(x,y,z)$ gives $f^{f^{f(x)}(y)+1}(z)=f(x+y+z+1)$. And $P(x,y,f(z))$ gives $f^{f^{f(x)}(y)+1}(z)=x+y+f(z)+1$. Therefore, $f(x+y+z+1)=x+y+f(z)+1$. Plugging in $y=z=1$ into the aforementioned gives $f(x+3)=x+2+f(1)$. Therefore, $f(x)=x+c$ for $x\ge 4$, for some constant $c$. Take some $x,y,z \ge 4$; then \[ f^{f^{f(x)}(y)}(z) = z+cf^{f(x)}(y)=z+c(y+cf(x))=z+cy+c^2x+c^3,\]so $P(x,y,z)$ gives $c^2x+cy+z+c^3=x+y+z+1$, which means $c=1$. Therefore, $f(x)=x+1$ for $x\ge 4$. We claim $f(x)=x+1$ for all $x$. Indeed, since \[ f^{f^{f(x)}(4)}(4) = 4+f^{f(x)}(4)=8+f(x),\]then $P(x,4,4)$ gives $8+f(x)=x+9$, hence $f(x)=x+1$, for all $x$.

MarkBcc168 wrote: Let $\mathbb{N}$ be the set of all positive integers. Find all functions $f : \mathbb{N} \to \mathbb{N}$ such that $$f^{f^{f(x)}(y)}(z)=x+y+z+1$$for all $x,y,z \in \mathbb{N}$. Proposed by William Wang. We claim that all functions which satisfy the given conditions are $\boxed{f(x) = x +1}$. Proof : Let $P(x, y, z)$ denote the statement of the problem. Suppose for some $a \neq b$ we have that $f(a) = f(b)$. Then comparing $P(x, y, a)$ and $P(x, y, b)$ for arbitrary naturals $(x, y)$ yield that $c + y + a + 1 = x + y + b + 1$ which means that the function is injective. Now, $P\left (x, y, f(z)\right ) \implies f^{f^{f(x)}(y)}(f(z)) = f(f^{f^{f(x)}(y)}(z)$ $ = x + y + f(z) + 1 = f(x + y + z +1)$. Now substituting $y = z = 1$ yields that $x + f(1) + 2 = f(x + 3)$. So, $f(4 + k) = f(4) + k$ for all $k \in \mathbb{N}_0$. But observe that using our injectivity, $f(1), f(2), f(3) < f(k)$ for all $k \geq 4$ and so $f(1), f(2), f(3) < f(1) + 3$. But, taking some $x, y, z \geq 4$ we then evaluate the results obtained by $P(x, y, z)$ which in fact is a equation which when simplified gives that $f(1) = 2$. But observe that there cannot exists $k$ such that $f(k) = 1$ or else $P(k, k, k)$ would imply that $1 = 1 + 3k$ which isn't possible for naturals which means that $\{ f(2), f(3) \} \in \{ 3, 4 \}$ with $f(2) \neq f(3)$ due to injectivity. Finally, it can be clearly seen that $f(2) = 3, f(3) = 4$ which finally proves our claim that $\boxed{f(x) = x+1}$ for all $x \in \mathbb{N}$

Let $P(x,y,z)$ denotes the given assertion. Observe first that if $a=f^{f(1)}(1)$, then $f^{(a)}(x)=x+3$ implies $f$ is injective. We now claim $f(k)\ge 2$ for every $k$. To see this, note that if $f(k_0)=1$ for some $k_0$, then $P(k_0,k_0,k_0)$ forces $1=3k_0+1$, absurd. Finally, compare $P(x,y,1)$ with $P(y,x,1)$. If there is a pair $(x,y)$ with $f^{f(x)}(y)\ne f^{f(y)}(x)$ then we obtain $1=f^{(t)}(x)$ for a suitable $t$ and $x$, which is again absurd as $1$ is not in the range. Thus $f^{f(x)}(y)=f^{f(y)}(x)$ for every $x,y$. Note that a consequence of injectivity is that if for some $a>b$ and $x,y$ it holds $f^{a}(x) = f^{b}(y)$, then $f^{a-b}(x)=y$ as well. Equipped with these facts we now proceed and establish $f(x)=x+1$ is the only solution. Step 1. $f(1)=2$: Note that $f^{f(x)}(1)=f^{f(1)}(x)$. If there is an $x$ with $f(x)<f(1)$ then $1=f^{f(x)-f(1)}(x)$, again absurd. Hence for every $x>1$, $f(x)>f(1)$ (injectivity) and $f^{f(x)-f(1)}(1)=x$. Thus $f$ is surjective on $[2,\infty)\cap \mathbb{N}$. In particular, there is an $n_0$ with $f(n_0)=2$, but as $f(1)$ is a lower bound on $f(n)$ for every $n>1$, this forces $f(1)=2$. Step 2. $f(2)=3$: We now have $f^{f(2)-f(1)}(1)=f(1)=2$. Again, if $f(2)>3$ then $f^{f(2)-3}(1)=1$, which is absurd. Thus $f(2)=3$ (note that $f(2)>f(1)=2$ by injectivity). Step 3. $f(n)=n+1$ for every $n\ge 1$. This is true for $n=1,2$. Now, $P(1,1,x)$ gives $f(f(f(x)))=x+3$, for every $x$. We now use induction. Assume $f(k)=k+1$ for every $1\le k\le n-1$. Now $P(1,1,n-2)$ gives $f(f(f(n-2)))=n+1$. $f(n-2)=n-1$ by inductive hypothesis, thus $f(f(f(n-2)))=f(f(n-1))$. Similarly, $f(n-1)=n$ again by inductive hypothesis. This forces $f(n)=n+1$, as requested.

We easily see that $f$ is quazi-surjective, hence $f^{f(1)}$ also is. Therefore there are values $w,w+1$ attained by $f^{f(1)}(y)$ as we vary $y$ (say at $y_1,y_2$. Which means $$f^w (z)=z+2+y_1 , f^{w+1}(z) =z+2+y_2$$ So, for all $ x \ge 3+y_1$, we have $f(x)= x+y_2 - y_1 = x+d$. Now the rest is just casework: Fixed $x$, for large $y$, $f^{f(x)}(y)= y+df(x)$. For large $z$, $$1+x+y+z = f^{y+df(x)}(z)= z+dy+d^2f(x)$$ , therefore $d=1$ and $f(x)=x+1$.To see this works, it is exactly the equality case in the last equation.

MarkBcc168 wrote: Let $\mathbb{N}$ be the set of all positive integers. Find all functions $f : \mathbb{N} \to \mathbb{N}$ such that $$f^{f^{f(x)}(y)}(z)=x+y+z+1$$for all $x,y,z \in \mathbb{N}$. Proposed by William Wang. You know there is a very short solution if we were to ask the same question with 0 as one of the natural numbers. Let x=y=z=0 we get that there exist a natural a with f(a)=1 so by letting x=y=a we get that f is linnear

Here's a really stupid solution. Set $x = y = 1$ and write $u = f^{f(1)}(1)$. We obtain that for all positive integers $n$ we have $f^u(n) = n+3$. Now we can spam arrows idea. The digraph of $f$ is a finite bunch of chains (at most $3$ chains). Let's say there are $c$ chains. The $cu$ "starting elements" must be precisely $1, 2, 3$ in some order, noticing that $u = 1$ is not possible since $f(n) = n+3$ is not a solution, we deduce that $c = 1$ and $u = 3$. Now there are at most $3! = 6$ functions satisfying the given relation and one can do simple casework to deduce that the only one that works is $1 \mapsto 2 \mapsto 3 \mapsto \dots$ or $f(n) = n+1$ for all positive integers $n$.

Same basic idea as the above solution By the assertion there exists a $c = f^{(f(1)}(1)$ such $f^{(c)}(x) = x + 3$, which also shows injectivity. Consider the unbounded sequence \[ \mathcal{S} = 1, f(1), f^{(2)}(1), f^{(3)}(1) \cdots \]Then, the sequences $n, f^{(c)}(n) = n + 3, f^{(2c)}(n) = n + 6, \cdots$ for $n = 4, 5, 6$ all have density $\frac{1}{c}$ in $\mathcal{S}$. Since they together have density $1$ in $\mathcal{S}$, it follows that $c = 3$. Now, with \[ \mathcal{S} = 1, f(1), f^{(2)}(1), 4 \cdots \]it follows that one of $f(1)$ and $f^{(2)}$ is $3$ by the definition of $c$. $f(1) = 3$ yields a contradiction which forces $f^{(2)}(3), f(1) = 2$. As such, $f(x) \equiv x + 1$ is the only solution.

The only solution if $f(n)=n+1$. We have \[ f(x+y+z+1) = f \left ( f^{f^{f(x)}(y)}(z) \right ) = f^{f^{f(x)}(y)}(f(z)) = x+y+f(z)+1 \] by symmetry we have $x+y+f(z)+1 = f(x+y+z+1) = f(x)+y+z+1$. So, $f(z)+x = f(x)+z$. Substituting $z=n+1$ and $x=n$ gives $f(n+1)-f(n)=1$ which implies that $f(n)=n+c$ for some constant $c$. Plugging this back in for $f$ gives \[ f^{f^{f(x)}(y)}(z) = x+cy+c^2z+c^3 \]thus, $c=1$ by matching coefficients. So, $f(n)=n+1$ is the only solution.

Potentially different solution. If $\mathcal{O}_n =\{n, f(n), f(f(n)),\ldots\}$ we remark that $\mathcal{O}_n$ is infinite, otherwise taking $y>\max_{m\in \mathcal{O}_n} m$ then $P(x,y,n)$ gives that $x+y+n+1\in \mathcal{O}_n$, a contradiction. Thus, for $a,b\geq 0$, $f^a(n)=f^b(n)\implies a=b$. Then $P(x,f(x),z)$ and $P(f(x),x,z)$ gives: $$f^{f^{f(x)}(f(x))}(z)=f^{f^{f(f(x))}(x)}(z)\implies f^{f(x)+1}(x)=f^{f(f(x))}(x)\implies f(f(x))=f(x)+1$$so since $x+y+z+1$ can take any integer value at least $4$, for all $n\geq 4$, we have $f(n)=n+1$. Then a quick check shows that for $\mathcal{O}_1,\mathcal{O}_2, \mathcal{O}_3$ to be infinite, we must have $f(1)=2,f(2)=3$ and $f(3)=4$ so $f(n)=n+1$ for all $n\in\mathbb N$ as needed.

Disclaimer: there's a decent chance I accidently fakesolved this. Disclaimer 2: in the undecent chance I didn't fakesolve this, there's a decent chance this is a super roundabout solution. Claim: $f(x) = x+1$ for sufficiently large $x$. Letting \[ x = f^{f(1)-1} (1), y = 1,\]we have that \[ f^4 (z) = c+z,\]where $c$ is some unknown, irrelevant constant. Letting \[ x = f^{f(1)-1} (1), y = 2,\]we have that \[ f^5 (z) = (c+1)+z,\]where $c$ is the same unknown, irrelevant constant. Hence, \[ f(c+z) = c+1+z\]for all $z \in \mathbb N$, implying that $f(x) = x+1$ for sufficiently large $x$. Claim: $f(x) = x+1$ for all $x$. If we plug sufficiently large $x$ and $y$ into the functional equation, we have \[ f^c (z) = z+c\]for sufficiently large constants $c$ and all $z \in \mathbb N$. Then, we have \[ z+c+1 = f^{c+1} (z) = f^c (f(z)) = f(z) + c, \]hence $f(z) = z+1$ for all $z$.

Motivated by the fff trick, we consider $$f(x + y +z + 1) = f^{f^{f(x)}(y)+1}(z) = f^{f^{f(x)}(y)}(f(z)) =x + y + f(z) + 1\quad (1),$$so $f(x) = x+c$, where $c = f(1)-1$. Then $$x + y + z + 1 = f^{f^{f(x)}(y)}(z) = f^{f^{x+c}(y)}(z) = f^{y + c(x+c)}(z) = z + c(y + c(x+c)),$$so $c =1$, and $f(x) = x + 1$ for $x\geq 4$ Additionally by $(1)$ we get $f(x + 3) = f(x) + 3$, so $f(1) = 1$, $f(2) = 3$ and $f(3) = 4$, thus $f(x) \equiv x+1$.

hi abcde orz . Notice that \[f^{x+y+z+1}(w)=f^{f^{f^{f(x)}(y)}(z)}(w)=f^{f^{f(f^{f(x)-1}(y))}(z)}(w)=f^{f(x)-1}(y)+z+w+1.\]First, setting $x=y=z=1$ gives $f^4(w)=f^{f(1)-1}(1)+w+2,$ so $f^4(w)=w+k$ for some $k,$ and setting $x=y=1,z=2$ gives $f^5(w)=f^{f(1)-1}(1)+w+3=w+k+1.$ Thus, for all $x>k$ we have $f(x)=x+1.$ Now suppose $x$ is any positive integer and $y,z>k.$ We have $f^{f(x)}(y)=y+f(x)$ by induction. We similarly get $f^{f^{f(x)}(y)}(z)=y+z+f(x),$ so we get $f(x)=x+1$ for all $x.$

Note that \[ f(x+y+z+1) = f^{f^{f(x)}(y)+1}(z) = f^{f^{f(x)}(y)}(f(z)) = x+y+f(z) + 1 \]By symmetry we also have $f(x) + y + z + 1 = x + y + f(z) + 1$. This implies that $f(x) + z = f(z) + x$ for any positive integers $x$ and $z$. In particular, then letting $z = x+1$ shows that $f(x) = x+c$ for some constant $c$. This implies that \[ x+y+z+1 = f^{f^{x+c}(y)}(z) = f^{y+cx+c^2}(z) = z + cy + c^2x + c^3 \]This must be true for any $(x, y, z)$ so then $c = 1$. Clearly, $f(x) = x+1$ works, as desired. $\blacksquare$

We can easily deduce that $f(x+y+z+1)=f(z)+x+y+1$ $P(z,1,2) \rightarrow f(z+4)=f(z)+4$ $P((z+1),1,1)\rightarrow f(z+4)=f(z+1)+3$ Hence $f(z+1)=f(z)+1$ so $f(x)=(x-1)+f(1) \forall x\in \mathbb{N}$ and a simple induction gives us $f^k(x)=x+k(f(1)-1)$. Plugging this in the original equation and solving the equation gives us $f(x)=x+1$ $$\mathbb{Q.E.D.}$$

Let $P(x,y,z)$ denote the assertion $f^{f^{f(x)}(y)}(z)=x+y+z+1$. Claim: $\boxed{f(x)=x+1}$ is the only solution. Proof. It is easy to verify that this works. Take $f$ on both sides. Since the composition is associative, we have $$f(x+y+z+1)=f\left(f^{f^{f(x)}(y)}(z)\right) = f^{f^{f(x)}(y)}(f(z))=x+y+f(z)+1.$$So, $f\left(P(x,y,z)\right) \equiv P\left(x,y,f(z)\right)$ and $f\left(P(z,y,x)\right) \equiv P\left(z,y,f(x)\right)$, which tells us that $f(x)+z=f(z)+x$. By induction, we see that $f(x)=x+c$ for some constant $c$. Substituting back in the original relation, we get $$x+y+z+1=c^2x+cy+z+c^3 \implies c=1.$$Therefore, $f(x)=x+1$ for all $x\in\mathbb{N}$ is the only solution, as desired. $\square$

Denote the assertion as $A(x,y,z)$. We claim with a few claims: FTSOC suppose $f(a)=1$ for some $a \in \mathbb{N}$. Then $A(a,a,a)$ gives a contradiction, so 1 is not in the range of $f$. Injectivity: If we have $f(a)=f(b)$, then we have $a=b$ from \[x+y+a+1 = f^{f^{f(x)}(y)-1} f(a) = f^{f^{f(x)}(y)-1} f(b) = x+y+b+1.\] We have $f^a(1) = f^b(1)$ iff $a=b$, as otherwise injectivity tells us $f^{|a-b|}(1) = 1$, contradiction. Substituting $A(x+1,1,1)$ and $A(x,2,1)$ combined with the previous result, we get \[f^{f(x+1)} (1) = f^{f(x)} (2).\] If $f(x+1) \leq f(x)$, we find $1 = f^{f(x)-f(x+1)} (2) \ge 2$, contradiction. Otherwise, we have $f^{f(x+1)-f(x)} (1) = 2$, so $f$ is linear. Substituting back in, we get our only solution $\boxed{f(x)=x+1}$, which evidently works. $\blacksquare$

Let $P(x,y,z)$ be the given assertion. Then, from $P(x,y,f(z))$ and $P(x,y,z),$ we have that $$x+y+f(z)+1 $$$$= f^{f^{x}(y)}(f(z)) $$$$= f^{f^{x}(y)+1}(z) $$$$= f\left(f^{f^{x}(y)+1}(z)\right) = f(x+y+z+1),$$implying that $f(x)$ is of the form $x+a,$ for some $a.$ Now, plugging this into the original equation, we find that the only solution is $f(x) = x+1.$

The only solution is $f(x) = x + 1,$ which works. Plug in $z = f(t)$ to get $$f^{f^{f(x)} (y) + 1} (z) = x + y + f(z) + 1.$$However, this is also equal to $$f(f^{f^{f(x)} (y)} (z)) = f(x+y+z+1),$$so $$f(x+y+z+1) = x+y+1+f(z)$$for all $x,y,z \in \mathbb{N}.$ In particular, we get $f(x+3) = f(x) + 3, f(x+4) = f(x) + 4,$ and $f(x+5) = f(x) + 5.$ Thus the first six values of $f$ are $$f(1), f(2), f(3), f(1) + 3, f(1) + 4 = f(2) + 3, f(1) + 5 = f(2) + 4 = f(3) + 3.$$Hence $f(2) = f(1) + 1, f(3) = f(2) + 1.$ Therefore, $f(x) = x + f(1) - 1.$ A quick check gives that $x+1$ is the only solution of the form $x+c$ that works, so we are done.

We clearly have that $f$ is surjective for all values above $3$. We also have that $f$ is injective. We also get that for all values $n\geq 2$ there must exist a value $k$ such $f^k(1)=n$. We also get that $f^f(y)f(x)= f^f(k)f(m)$ if $x+y=k+m$, thus because everything is in a chain, we get that $f^{f(x+y-1)}f(1)$, is equal to all those values and as there are $x+y-1$ of those values we get $f(x+y-1)> x+y-1$. Thus we get the function is increasing, and clearly this only works if $f(x)=x+1.

7 minute solve Observe that $f(x+y+z+1)=f^{f^{f(x)}(y)+1}(z)=f^{f^{f(x)}(y)}(f(z))= x+y+f(z)+1 \stackrel{\text{sim}}= x+f(y)+z+1$ which means that $f(z)-z = f(y)-y$ for all $y,z \in \mathbb N$ which means $f(x)= x+c$ for some $c$. Testing $f(x) = x+c$ we get $f^{f^{f(x)}(y)}(z) = f^{f^{x+c}(y)}(z) = f^{y+cx+c^2}(z) = z+cy+c^2x+c^3=x+y+z+1$ which means that $c=1$ or $f(x)=x+1$.