Iterated FE on positive integers

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarkBcc168

1593 posts

MarkBcc168

#1 h Jul 28, 2020, 7:44 AM • 3 Y

Y by Euler01, samrocksnature, megarnie

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.

This post has been edited 2 times. Last edited by MarkBcc168, Jan 2, 2021, 1:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeoMetrix

924 posts

GeoMetrix

#2 h Jul 28, 2020, 7:44 AM • 17 Y

Y by Math-wiz, amar_04, srijonrick, mijail, Deemaths, somebodyyouusedtoknow, A-Thought-Of-God, biomathematics, snakeaid, samrocksnature, math31415926535, Chokechoke, Vladimir_Djurica, Sedro, soryn, aidan0626, MS_asdfgzxcvb

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Omega18

161 posts

Omega18

#3 h Jul 28, 2020, 7:45 AM • 5 Y

Y by Deemaths, samrocksnature, Zaro23, sophiawang85, soryn

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Severus

742 posts

Severus

#4 h Jul 28, 2020, 7:56 AM • 2 Y

Y by samrocksnature, soryn

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$

This post has been edited 1 time. Last edited by Severus, Aug 3, 2020, 5:32 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathematicsislovely

245 posts

Mathematicsislovely

#5 h Jul 28, 2020, 8:13 AM • 5 Y

Y by samrocksnature, Mango247, Mango247, Mango247, soryn

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$

This post has been edited 1 time. Last edited by Mathematicsislovely, Jul 28, 2020, 12:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Googolplexian

56 posts

Googolplexian

#6 h Jul 28, 2020, 8:59 AM • 2 Y

Y by samrocksnature, soryn

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Plops

946 posts

Plops

#7 h Jul 28, 2020, 12:40 PM • 1 Y

Y by samrocksnature

Bash

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ghu2024

951 posts

ghu2024

#8 h Jul 28, 2020, 12:59 PM • 1 Y

Y by samrocksnature

Wrong

This post has been edited 3 times. Last edited by ghu2024, Sep 18, 2020, 9:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lilavati_2005

357 posts

lilavati_2005

#9 h Jul 28, 2020, 1:09 PM • 1 Y

Y by samrocksnature

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lrjr24

966 posts

lrjr24

#10 h Jul 28, 2020, 1:09 PM • 1 Y

Y by samrocksnature

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blacksheep2003

1081 posts

blacksheep2003

#11 h Jul 28, 2020, 1:13 PM • 1 Y

Y by samrocksnature

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Physicsknight

635 posts

Physicsknight

#12 h Jul 28, 2020, 2:20 PM • 1 Y

Y by samrocksnature

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

franchester

1487 posts

franchester

#13 h Jul 28, 2020, 2:28 PM • 3 Y

Y by samrocksnature, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Lcz

390 posts

Lcz

#14 h Jul 28, 2020, 2:37 PM • 1 Y

Y by samrocksnature

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 ;-;

This post has been edited 1 time. Last edited by Lcz, Jul 28, 2020, 2:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#15 h Jul 28, 2020, 5:00 PM • 2 Y

Y by samrocksnature, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NoctNight

108 posts

NoctNight

#54 h Jun 14, 2023, 6:08 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihatemath123

3435 posts

ihatemath123

#55 h Jul 18, 2023, 6:08 AM

Y by

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

This post has been edited 3 times. Last edited by ihatemath123, Jul 18, 2023, 12:41 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AtharvNaphade

341 posts

AtharvNaphade

#56 h Aug 19, 2023, 8:52 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1724 posts

OronSH

#57 h Nov 24, 2023, 10:08 PM • 2 Y

Y by mathmax12, megarnie

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abeot

123 posts

abeot

#58 h Nov 25, 2023, 7:12 PM • 1 Y

Y by centslordm

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Cusofay

85 posts

Cusofay

#59 h Feb 6, 2024, 5:51 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sammy27

81 posts

Sammy27

#60 h Feb 12, 2024, 1:59 PM • 1 Y

Y by Eka01

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$

This post has been edited 1 time. Last edited by Sammy27, Feb 12, 2024, 2:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

792 posts

shendrew7

#61 h Feb 24, 2024, 11:52 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mr.Sharkman

487 posts

Mr.Sharkman

#62 h May 27, 2024, 10:54 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicBird08

1735 posts

EpicBird08

#63 h Aug 18, 2024, 2:22 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

N3bula

254 posts

N3bula

#64 h Oct 6, 2024, 1:14 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

973 posts

bjump

#65 h Oct 15, 2024, 12:06 AM • 1 Y

Y by OronSH

7 minute solve :wacko:

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

300 posts

Ilikeminecraft

#66 h Jan 25, 2025, 11:13 PM

Y by

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.$ Taking $y = z = 1$ into our new equation, we get that for $x\geq4,$ the function is linear. By taking $y = 1,$ and $z = 2, 3,$ we get that $f$ is linear. let $f(x)= x + c$ then, $f^{f^{f(1)}(1)}(1) = f^{1 + c + c^2}(z) = 1 + c + c^2 + c^3 = 4,$ and so $(c - 1)(c^2 + 2c + 3) = 0,$ which finishes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

quantam13

96 posts

quantam13

#67 h Feb 23, 2025, 9:32 AM

Y by

Let $P(x,y,z)$ denote the given assertion. $P(x,y,f(z))$ gives that $f(x+y+z+1)=x+y+f(z)+1=f(x)+y+z+1$ and hence we have that $f(x)-x$ is some constant $c$ but if $c\neq 1$ its easy to get a contradiction and its also easy to get that $c=1$ gives us a valid solution. Hence we have that $\boxed{f(x)=x+1}$ is the only solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3363 posts

pi271828

#68 h Mar 18, 2025, 2:13 AM

Y by

The answer is $f(x) = x+1$ only.

Claim: $f$ is injective

Proof. Take $f(a) = f(b)$ and note $\begin{align*} f^{f^{f(a)}(a)}(a)=3a+1 = f^{f^{f(b)}(b)}(b) = 3b+1\end{align*}$ so $f$ is injective. $\square$

Claim: $f(x) > 1$

Proof. For contradiction, suppose there is some $c > 0$ such that $f(c) = 1$ . From the assertion, we have $\begin{align*} f^{f^{f(c)}(c)}(c) = 3c+1 = 1 \end{align*}$ This implies $c=0$ , bad. $\square$

Claim: $f^{f(m)}(1) = f^{f(1)}(m)$

Proof. Assume for contradiction this is not the case. From $P(m, 1, 1)$ and $P(1, m, 1)$ , we receive that $\begin{align*} f^{f^{f(m)}(1)}(1) = m+3 = f^{f^{f(1)}(m)}(1)\end{align*}$ Now by invoking injectivity, we must have $\begin{align*} f^{\left | f^{f(m)}(1) - f^{f(1)}(m)\right |}(1) = 1\end{align*}$ which gives us the desired contradiction. $\square$

Claim: $f(m) > f(1)$

Proof. For contradiction, assume not. Then by injectivity, we must have $\begin{align*} f^{f(1) - f(m)}(m) = 1\end{align*}$ which gives us the desired contradiction. $\square$

Claim: $f(1) = 2$

Proof. From injectivity, the previous claim reduces to $f^{f(m) - f(1)}(1) = m$ for all $m > 0$ . Note that there clearly must be a $c$ such that $f(c) = 2$ , and since $f(m) > f(1) \ge 2$ , we must have $f(1) = 2$ . $\square$

Claim: $f(x) = x+1$ for all $x$

Proof. We finish with induction. Assume $f(x) = x+1$ for all $x < k$ . From setting $m = k-1$ , we get $f^{k-2}(1) = k-1$ . Now take the integer $m$ such that $f(m) = k+1$ and plug this in. We have that $m = f^{k-1}(1) = f(k-1) = k$ , done. $\square$

Z K Y