Find all injective functions $ f:\mathbb{N} \to \mathbb{N} $ such that $$ f^{f\left(a\right)}\left(b\right)f^{f\left(b\right)}\left(a\right)=\left(f\left(a+b\right)\right)^2 $$holds for all $ a,b \in \mathbb{N} $. Note that $ f^{k}\left(n\right) $ means $ \underbrace{f(f(\ldots f}_{k}(n) \ldots )) $
Problem
Source: 2017 Taiwan TST Round 1, Day 4, Problem 3
Tags: algebra, functional equation
14.04.2017 20:47
Is $RHS f^2(a+b)$ or $f((a+b)^2)$?
14.04.2017 23:09
15.04.2017 03:34
Lol, when you work on an FE for 2 hours on the non-injective case, then think to yourself, "you know what's the worst? Those times when you are solving an fe and forget to read that it is injective...but that would be ridiculous here." then you check the site and it says it's injective. Rip 2 hours I could've been doing other things...
15.04.2017 17:08
Is there any other solution if we don't assume it's injective?
15.04.2017 17:18
Certainly, there are many non-injective functions satisfying the equation. For example, all constant functions and $ f: \mathbb{N} \to \mathbb{N} $ defined by the following rules: $$ f\left(1\right) \ \text{is an arbitrary number bigger than $ 1 $ and} \ \ f\left(n\right)=133, \forall n \ge 2 $$
16.04.2017 04:42
22.04.2020 02:13
Great problem! We claim that the only solution is $f(n) = n + 1$, which can be checked to work. We now show it is the only solution. Let $P(a, b)$ denote the given assertion. We first show that $1$ is not in the image of $f$. Indeed, suppose there exists a positive integer $u$ such that $f(u) = 1$. From $P(u, u)$, we deduce that \begin{align*} f^{f(u)}(u)^2 &= f(2u)^2 \\ f^{f(u)}(u) &= f(2u) \\ 1 &= f(2u). \end{align*}Hence, $f(2u) = f(u)$, contradicting injectivity (as $u$ is a positive integer). This proves the claim. The key part of the solution is to prove that $f(1) = 2$ and $f(2) = 3$. From $P(a, a)$, we now deduce that \begin{align} f^{f(a)}(a)^2 &= f(2a)^2 \nonumber \\ f^{f(a)}(a) &= f(2a) \nonumber \\ f^{f(a) - 1}(a) &= 2a. \end{align}In particular, this implies that all even numbers are in the image of $f$. Let $k$ be the positive integer for which $f(k) = 2$ (which is unique by injectivity). Suppose $k > 1$. Then, from $P(k - 1, 1)$, we have \begin{align*} f^{f(k - 1)}(1)f^{f(1)}(k - 1) &= f(k)^2 = 4 \\ \implies f^{f(k - 1)}(1) &= f^{f(1)}(k - 1) = 2, \end{align*}where the implication holds because $f(n) > 1$ for all $n$. From (1), $f^{f(1) - 1}(1) = 2$, we have \begin{align*} f^{f(1) - 1}(1) &= f^{f(1)}(k - 1) \\ f(k - 1) &= 1, \end{align*}a contradiction (where the second equality follows upon taking inverses $f(1) - 1$ times). Thus, we must have $k = 1$, so $f(1) = 2$. Now, from $P(1, 2)$, we have \begin{align*} f^{f(1)}(2)f^{f(2)}(1) &= f(3)^2. \end{align*}Additionally, note (by (1)) that \begin{align*} f^{f(2)}(1) = f^{f(2) - 1}(f(1)) = f^{f(2) - 1}(2) = 4. \end{align*}Hence, $4 \mid f(3)^2$, so $f(3)$ is even. Hence, by (1), $f^{f(3) / 2 - 1}(f(3) / 2) = f(3)$, which implies by injectivity that $3$ is in the image of $f$. Redefine $k$ to be the positive integer for which $f(k) = 3$ (which is, again, unique by injectivity). Suppose $k > 2$. If $k = 3$, we have $f^{f(3) - 1}(3) = 3 = 6$, absurd. Hence, $k > 3$. Now, from $P(k - 3, 3)$, we have \begin{align*} f^{f(k - 3)}(3)f^{f(3)}(k - 3) &= f(3)^2 = 9 \\ \implies f^{f(k - 3)}(3) &= f^{f(3)}(k - 3) = 3. \end{align*}Hence, \begin{align*} f^{f(k - 3)}(3) &= f(k) \\ f^{f(k - 3)}(f(k)) &= f(k) \\ f^{f(k - 3) + 1}(k) &= f(k). \end{align*}This is enough to imply that the sequence $\{f^i(k)\}_{i = 0}^\infty$ is periodic (since $f(k - 3) + 1 > 0$). However, by iterating (1), we find that this sequence contains $2^mk$ for all $m > 0$, so the sequence is unbounded, meaning that it cannot be periodic. Thus, we have $k \leq 2$. Since $f(1) = 2 \neq 3$, it follows that in fact $f(2) = 3$. We are past the hard part now -- all that is left is an easy induction. We will prove by induction that $f(n) = n + 1$ for all $n \in \mathbb{N}$. The base cases $n = 1, 2$ are done, so suppose the result is true for all $m' < 2m - 1$, where $m \geq 2$ is a positive integer. We will show it is true for $2m - 1$ and $2m$ as well. From (1), we have \begin{align*} f^{f(m) - 1}(m) &= 2m \\ f^m(m) &= 2m \\ f(2m - 1) &= 2m, \end{align*}proving the result for $2m - 1$. Note that $f^{2m - 1}(1) = 2m$, so $f^{2m}(1) = f(2m)$. From $P(2, 2m - 1)$, we have \begin{align*} f^{f(2)}(2m - 1)f^{f(2m - 1)}(2) &= f(2m + 1)^2 \\ f^{3}(f^{2m - 2}(1))f^{2m}(f(1)) &= f(2m + 1)^2 \\ f^{2m + 1}(1)^2 &= f(2m + 1)^2 \\ f^{2m + 1}(1) &= f(2m + 1) \\ f(f^{2m}(1)) &= f(2m + 1) \\ f(f(2m)) &= f(2m + 1), \end{align*}so by injectivity, $f(2m) = 2m + 1$. Therefore, the result is true for $2m$ as well, completing the induction. Thus, $f(n) = n + 1$ is the only solution to the given equation, as claimed. $\Box$
15.06.2020 17:43
Not easy. Denote $P(a,b): f^{f\left(a\right)}\left(b\right)f^{f\left(b\right)}\left(a\right)=\left(f\left(a+b\right)\right)^2$. $P(a,a)$ implies $f^{f(a)}(a)=f(2a)$ and $f^{f(a)-1}(a)=2a$ $(*)$. Consider $f_{n,i}=f^{i}(n)$. If there is a positive $i$ such that $f_{n,i}=n$, then sequence $f_{n,1},f_{n,2},\dots$ is periodic, therefore it has finite possible values. However, $(*)$ implies $2^jn$ is in this sequence, for all positive integer $j$. Contradiction! $(\dagger)$ By $(*)$, there is a positive integer $t$ such that $f(t)=2$. By $(*)$, $f(2t)=f^{f(t)}(t)=f^2(t)=f(2)$, so $t=1$. We have $f(1)=2$. If there exists a positive integer $s$ such that $f(s)=1$, $s\ge 2$. $P(s-1,1)$ gives us $f^{f(s-1)}(1)=1$, contradicting with argument $(\dagger)$. Such $s$ doesn't exist. $(\bullet)$ Suppose that $f(2)=k$. $P(1,2)$ gives us $f(3)^2=f^2(2)f^{f(2)}(1)=f(k)f^{f(2)-1}(2)=4f(k)$. So $f(k)=x^2$ is a perfect square and $f(3)=2x$ ($x\in\mathbb{N}$, $x\ge 2$). By $(*)$, $f^{f(x)-1}(x)=2x$, and $f\left(f^{f(x)-3}(x)\right)=3$, $(f(x)\ge 3)$. $P(1,f^{f(x)-3}(x))$ gives us $f(1+f^{f(x)-3}(x))^2=f(3)f^{3}(1)=2x^3$. So $2x^3$ is a perfect square. We have $x=2y^2$, $y\in\mathbb{N}$. By $(*)$, $f^{f(y^4)+f(2y^4)-2}(y^4)=f^{f(2y^4)-1}(2y^4)=4y^4=f(k)$. If $f(y^4)+f(2y^4)-2\ge 4$, we have $f(f^{f(y^4)+f(2y^4)-6}(y^4))=1,$ contradicting with $(\bullet)$. On the other hand, $f(y^4)+f(2y^4)-2\ge 2+3-2=3$, and the equality holds iff $\{f(y^4),f(2y^4\}=\{2,3\}$. Thus $y=1, x=2$, $f(3)=2x=4, f(k)=x^2=4$, so $k=3$. We get $f(2)=3, f(3)=4$. Now we proceed with induction on $a$ to show that $f(a)=a+1$. Base cases $a=1,2,3$ are done. When $a\ge 4$, $P(2,a-1)$ gives us $f(a+1)^2=f^{a}(2)f^3(a-1)=f^2(a)f^{2}(a)$. So $f(a+1)=f(f(a))$, $f(a)=a+1$. Clearly $f(a)=a+1$ is indeed a solution. So the answer is $f(a)=a+1$.
26.09.2020 16:43
FEcreater wrote: Find all injective functions $ f:\mathbb{N} \to \mathbb{N} $ such that $$ f^{f\left(a\right)}\left(b\right)f^{f\left(b\right)}\left(a\right)=\left(f\left(a+b\right)\right)^2 $$holds for all $ a,b \in \mathbb{N} $. Note that $ f^{k}\left(n\right) $ means $ \underbrace{f(f(\ldots f}_{k}(n) \ldots )) $ Fantastic problem! Firstly, $f(n) = n + 1$ clearly satisfies the problem as both sides equal to $(a + b + 1)^2$. We will prove that this is the only function. Denote $P(x,y)$ as the assertion of $x$ and $y$ to the given functional equation. Now, $P(a,a)$ gives us $f^{f(a) - 1}(a) = 2a$. $\textbf{Claim 01.}$ There doesn't exist a value $n$ such that $f(n) = 1$. $\textit{Proof.}$ Suppose otherwise, then $2n = f^{f(n) - 1}(n) = n$, a contradiction. Now, we want to find the values of $f(2)$ and $f(3)$. $P(1,2)$ gives us $f^{f(1)}(2) \cdot f^{f(2)}(1) = f(3)^2$. But since $f^{f(2)}(1) = f^{f(2) - 1}(2) = 4$, then $2 \mid f(3)$. Thus, we have $f^{\frac{f(3)}{2} - 2} \left( \frac{f(3)}{2} \right) = 3$. Therefore there exists a value $n$ such that $f(n) = 3$. We claim that $n = 2$. Suppose otherwise, that $n \ge 3$, we can consider $P(1,n - 1)$: \[ f^2(n - 1) \cdot f^{f(n - 1)}(1) = f(n)^2 = 9 \]Therefore, we have $f(f(n - 1)) = 3 = f(n) \rightarrow f(n - 1) = n$. Consider $P(2,n - 2)$, we then have \[ f^{f(n - 2)}(2) \cdot f^{f(2)}(n - 2) = f(n)^2 = 9 \]Thus, we have $f^{f(n-2)}(2) = 3 = f^{f(n-1)}(1)$, this forces $f(n - 2) + 1 = f(n - 1) = n$. Therefore, $f(n - 2) = n - 1$. Hence, $f^{f(2)}(n-2) = f^{f(2) - 1}(n - 1) = f^2(n - 1)$ gives us $f(2) - 1 = 2$, which means $f(2) = 3$. This gives us $n = 2$, a contradiction. Now, we have $f^{f(2) - 1}(2) = 4$ which gives $4 = f^2(2) = f(3)$. Therefore, we have $f(1) = 2, f(2) = 3, f(3) = 4$. We will now prove that $f(n) = n + 1$ for all $n \in \mathbb{N}$ by strong induction. Suppose that $f(n) = n + 1$ for all $n \le k$. We divide two cases: $\textbf{Case 01.}$ If $k$ is even. $\textit{Proof.}$ Notice that $f^{f \left( \frac{k + 2}{2} \right) - 1} \left( \frac{k + 2}{2} \right) = k + 2$, however we know that $f \left( \frac{k + 2}{2} \right) - 1 = \frac{k + 2}{2}$, and $f^a \left( \frac{k + 2}{2} \right) = \frac{k + 2}{2} + a$ for all $a \le \frac{k}{2}$. Thus, we have $f (k + 1) = k + 2$ in this case. We have finished the induction case. $\textbf{Case 02.}$ If $k$ is odd. $\textit{Proof.}$ Let $k = 2a + 1$. Therefore, we know that from $P(a + 2 ,a+1)$ then $f^{f(a + 2)}(a + 1) \cdot f^{f(a + 1)}(a + 2) = f(2a + 3)^2$. Therefore, we have $f^{a + 3}(a + 1) \cdot f^{a + 2}(a + 2) = f(2a + 3)^2$. Therefore, we have $f^2(2a + 2) \cdot f^2 (2a + 2) = f(2a + 3)^2$, which forces $f^2(2a + 2) = f(2a + 3)$, which therefore gives $f(k) = k + 1$. Induction complete.
28.10.2020 16:19
Solved with amuthup I claim that the only solution is $f(a) = a+1.$ As usual, let $P(a,b)$ denote the problem statement. $P(a,a)$ gives $\left(f^{f(a)}(a)\right)^2 = \left(f(2a)\right)^2 \implies f^{f(a)}(a) = f(2a) \implies f^{f(a)-1}(a) = 2a \implies f(1) = 2$ since $f$ is injective. Note that if we let $a+b = n,$ then $f(n)^2 = f^{f(n-k)}(k)f^{f(k)}(n-k) = f^{f(n-i)}(i)f^{f(i)}(n-i)$ for $i, k \in \{1, \dots, n-1\}.$ This implies that $f^{f(1)}(n-1)f^{(n-1)}(1) = f^{f(2)}(n-2)f^{(n-2)}(2).$ Since $f(2) = f^2(1),$ we have $f^{(n-1)}(1) = f^{(n-2)}(2) \implies f^{f(1)}(n-1) = f^{f(2)}(n-2).$ Taking $n = 3$ gives $f^{f(1)}(2) = f^{f(2)}(1) = f^{f(2)-1}(2) \implies f(2)-1 = f(1) \implies f(2) = 3$ as long as $\{f^{(i)}\}_{i > 0}$ doesnt have any repeated values, which is the same as being non-periodic. We now prove that the sequence $\{f^{(i)}\}_{i > 0}$ isn't periodic. If the sequence happens to be periodic, then there are only finitely many values. But since $f^{f(a)-1}(a) = 2a,$ all evens must be in the sequence, a contradiction. Now, recall that $f^{f(1)}(n-1) = f^{f(2)}(n-2) \implies f^{2}(n-1) = f^{3}(n-2) \implies n-1 = f(n-2),$ which implies the desired result.
07.12.2020 11:52
Taiwan TST 2017 Round 1 Day 4 P3 wrote: Find all injective functions $ f:\mathbb{N} \to \mathbb{N} $ such that $$ f^{f\left(a\right)}\left(b\right)f^{f\left(b\right)}\left(a\right)=\left(f\left(a+b\right)\right)^2 $$holds for all $ a,b \in \mathbb{N} $. Note that $ f^{k}\left(n\right) $ means $ \underbrace{f(f(\ldots f}_{k}(n) \ldots )) $ Let $P(x,y)$ be the given assertion (replace $a,b$ with $x,y$). Note that $P(x,x) \Rightarrow f^{f(x)} (x)=f(2x),$ and since $f$ is injective we conclude that $f^{f(x)-1}=2x \,\, (*)$ for all $x$. Hence, $f$ is surjective on evens, and $f(x) \geq 2$ for all $x$. We prove some Claims. Claim 1: $f(1)=2$. Proof: Let $k$ be such that $f(k)=2$. Then, $x=k$ in $(*)$ implies that $f(k)=2k \Rightarrow k=1$. Therefore, $f(1)=2,$ as desired $\blacksquare$. Claim 2: $f(3)=4$. Proof: Let $\ell$ be such that $f(\ell)=4$. Suppose firstly that $\ell \geq 4$. Note that $P(1, \ell -1 )$ implies $$f(f(\ell-1))f^{f(\ell-1)}(1)=f(\ell)^2=16$$Since both factors are divisors of $16$ and $>1$, we have $f(f(\ell-1)) \in \{2,4,8 \}$. If $f(f(\ell-1))=2$, then $f(f(\ell-1))=2=f(1)$, hence $f(\ell-1)=1$, contradiction. If $f(f(\ell-1))=8$, then $f^{f(\ell-1)}(1)=2=f(1)$, hence $f^{f(\ell-1)-1}(1)=1$, contradiction. Thus, $f(f(\ell-1))=f^{f(\ell-1)}(1)=4$. Hence, $$f(f(\ell-1))=4=f(\ell) \Rightarrow f(\ell-1)=\ell$$therefore $$f^{\ell}(1)=4=f(\ell) \Rightarrow f^{\ell-1}(1)=\ell=f(\ell-1) \Rightarrow f^{\ell-1}(1)=\ell-1$$ Therefore, $P(f^{\ell-3}(1),1)$ implies $$f^{\ell-1}(1)=f(f^{\ell-3}(1)+1) \Rightarrow f^{\ell-3}(1)+1=\ell -1 \Rightarrow f^{\ell-3}(1)=\ell-2 \Rightarrow f(\ell-2)=\ell-1$$Similarly, $P(f^{\ell-4}(1),1)$ implies $f(\ell-3)=\ell-2,$ hence continuing like that we obtain $f(\ell-k)=\ell-k+1$, for all $1 \leq k \leq \ell-1$. Since $\ell \geq 4$, we may take $k=\ell -3 \geq 1$ in the above to obtain $f(3)=4=f(\ell) \Rightarrow \ell=3$, contradiction. Therefore, $\ell \leq 3$, that is $\ell \in \{2, 3 \}$. If $\ell=2$, then $f(2)=4$. Take $x=2$ in $(*)$ to obtain $$f(f(f(2)))=4=f(2)=f(f(1)) \Rightarrow f(2)=1,$$contradiction. Thus, $\ell=3$, hence $f(3)=4,$ as desired.$\blacksquare$. Claim 3: $f(2)=3$. Proof: From the above, $f(\ell)=4 \Rightarrow f(\ell-1)=\ell$. Since $\ell=3$, we conclude that $f(2)=3$ $\blacksquare$ To end, we perform strong induction to prove that $f(x)=x+1$ for all $x$. Suppose that $f(x)=x+1$ for all $x<n$. Then, $$P(n-1,2) \Rightarrow f^n(2)f(f(f(n-1)))=f^2(n+1) \Rightarrow f(f(n))=f(n+1) \Rightarrow f(n)=n+1,$$as desired. Therefore, $f(x)=x+1$ is our only solution, as it obviously satisfies the given assertion.
22.10.2021 10:27
A different solution: (the main step is after the last lemma, till that it is similar to the above solutions) The answer is $f(x) \equiv x+1$, which clearly works. Now we show this is the only solution. Let $P(a,b)$ be the given assertion. $$P(a,a) ~:~ f^{f(a)}(a) = f(2a) \qquad{(1)}$$ Claim: $f(1) = 2$. Proof: Taking $a=1$ in $(1)$ along with injectivity of $f$ gives $f(\beta) = 2$ for some $\beta \in \mathbb Z_{>0}$. Then $a = \beta$ in $(1)$ gives $f(2) = f(2 \beta)$, so injectivity of $f$ forces $\beta = 1$. $\square$ Lemma: $f(\alpha) \ne 1$ for all $\alpha \in \mathbb Z_{>0}$. Proof: Suppose not. Then $\alpha \ne 1$ becasue of our previous claim. Taking $a= \alpha$ in $(1)$ forces $f(2 \alpha) = 1 = f(\alpha)$, contradicting the injectivity of $f$. $\square$ Lemma: For any $c,d \in \mathbb Z_{>0}$, we \textbf{cannot} have $f^d(c) = c$. Proof: Suppose not. Call a number \emph{good} if it can be represented at $f^k(c)$ for some $k \in \mathbb Z_{>0}$. Then because are assumption, number of good numbers must be finite. But $(1)$ gives that all of $2c,4c,8c,16c,\ldots$ are good, which is a contradiction. This proves our lemma. $\square$ Now comes the clever part of the problem: Define the sequence $\delta_0,\delta_1,\delta_2,\ldots$ of positive integers such that the following conditions hold: $$\delta_0 = 1 ~~,~~ f(\delta_{i+1}) = \min \Big( \{f(1),f(2),f(3),\ldots\} \setminus \{f(\delta_0),f(\delta_1),\ldots,f(\delta_i) \} \Big)$$As $f$ is injective, so our sequence is well defined ; all its elements are distinct ; and moreover, it must contain all positive integers. So it suffices to prove the following claim: Claim: For any $i \ge 1$, $f(\delta_i-1) = \delta_i$ and $f^{f(\delta_i) - 1}(1) = f(\delta_i)$ Proof: We use strong induction. The proof of base case is isomorphic to the inductive step, so we directly move onto it. Assume the assertion holds for all $i \le k$ (for some $k \in \mathbb Z_{>0}$). Taking $a = \delta_{k+1} - 1$ in $(2)$ gives $$f^{f(\delta_{k+1}) - 1}(1)f(f(\delta_{k+1} - 1)) = f(\delta_{k+1})^2 \qquad{(3)}$$From injectivity of $f$, the second term on the LHS is not equal to $f(\delta_j) = f(f(\delta_j - 1))$ for any $j \in \{1,\ldots,k\}$ (for $j=0$, we use our first lemma). The first term on the LHS cannot equal $f(\delta_j) = f^{f(\delta_j) - 1}(1)$ for any $j \in \{0,1,\ldots,k\}$ because of our second claim. So it follows that both terms on the LHS are $\ge f(\delta_{k+1})$, which forces both of them to equal $f(\delta_{k+1})$, completing our inductive step. $\square$ This completes the proof of the problem. $\blacksquare$
03.01.2022 05:27
The answer is $f(x)\equiv x+1$, which clearly works. Claim 1: If $f^a(b)=f^c(d)$ and $a>c$ then $f^{a-c}(b)=d$. Proof: Let $k=f^{a-c}(b)$. We have $f^c(k)=f^c(d)$. We can prove via induction on $m$ that $f^m$ is injective, so $k=d$, as desired. This implies the (infinite) graph $x\rightarrow f(x)$ is a disjoint union of acyclic chains because $P(a,a)$ yields $f^{f(a)}(a)=f(2a)$. By claim 1, $f^{f(a)-1}(a)=2a$, so any number $a$ can reach $2^ka$ in its chain, implying there are no cycles in $f$. Claim 2: $f(1)=2$ Proof: Let $t=f^{f(1)-2}(1)$. We know $f(1)>1$ because $f$ has no cycles (in fact, $f(x)\ne 1$ for any $x$, or otherwise $P(x,x)$ gives $f^{f(x)}(x)=f(2x)$ but $f^{f(x)}(x)=f(x)=1$ so $f(2x)=1$, so $f$ is not injective). If $f(1)\ne 2$ then $t>1$ $P(1,t-1)$ gives $f^{f(1)}(t-1) \cdot f^{f(t-1)}(1) = f(t)^2$ Note $f(t)=f^{f(1)-1}(1)=2$ so RHS=4 Since 1 is not in the range of $f$, $f^{f(t-1)}(1)=2$ and $f^{f(1)}(t-1)=2$. Since $f$ is acyclic and $f^{f(t-1)}(1)=f^{f(1)-1}(1)=2$, we know $f(t-1)=f(1)-1$ (recall $t>1$) Note $f^{f(1)-1}(f(1)-1)=f^{f(1)}(t-1)=2=f^{f(1)-1}(1)$. Therefore, $f(1)-1=1$, as needed. Claim 3: $f(2)=3$. Proof: Let $t=f^{f(2)-2}(2)$. Since $f(2)>2$ we can see $t\ge 3$. Also, $f(t)=4$. $P(2,t-2)$ yields $f^{f(t-2)}(2) f^{f(2)}(t-2)=16$. We know $f^{f(t-2)}(2)\ge 4$. If $f^{f(2)}(t-2)=1$ then $f(2)=0$, contradiction. If $f^{f(2)}(t-2)=2$ then by our previous claim $f^{f(2)-1}(t-2)=1$ which implies $f(2)-1=0$. Therefore, $f^{f(t-2)}(2)=f^{f(2)}(t-2)=4$. We analogously get $f(t-2)=f(2)-1$ so $f^{f(2)-1}(f(2)-1)=f^{f(2)-1}(2)=4$, so $f(2)=3$ and $f(3)=4$. Repeating the same argument gives $f(4)=5$. Claim 4: $f(n)=n+1$ for all $n$. Assume $f(n-1)=n$. Case 1: $n=2k$ is odd. Then $P(k,k+1)$ gives $f^{f(k+1)}(k)f^{f(k)}(k+1)=f(2k+1)^2$ $f^{k+1}(k+1)=f(2k+1)$ $f^2(2k)=f(2k+1)$ $f(2k)=2k+1$. Case 2: $n=2k$ is even. Then $P(k,k)$ gives $f^{k+1}(k)=f(2k)$ but $f^{k+1}(k)=f^2(2k-1)$, so we are done. Lesson Learned: I spent too much time trying to look at $a+b=p$ case with that same argument. However, I was stuck with the case $f^{f(t-p)}(p)=4p$ and $f^{f(p)}(t-p)=p$. There is actually no clean solution. Furthermore, knowing $f(p)=p+1$ is not that useful at all. Therefore, I stepped back to see if I can use induction or something similar. That works.
22.01.2023 05:51
Find all injective functions $ f:\mathbb{N} \to \mathbb{N} $ such that$$ f^{f\left(a\right)}\left(b\right)f^{f\left(b\right)}\left(a\right)=\left(f\left(a+b\right)\right)^2 $$holds for all $ a,b \in \mathbb{N} $. Note that $ f^{k}\left(n\right) $ means $ \underbrace{f(f(\ldots f}_{k}(n) \ldots )) $ The only solution is $\boxed{f(x) = x+1}$, which works. Let $P(a,b)$ denote the given assertion. Claim: $f(x)\ne 1$ for all $x$. Proof: Suppose $f(k) = 1$ for some $k$. $P(k,k): f(k) = f(2k)\implies k =2k $, contradiction. $\square$ Claim: $f(1) = 2$. Proof: Suppose not. Notice that if $f(x) = 2$, then $P(x,x): f(f(x)) = f(2x)$, so $f(x) = 2x\implies x=1$. To see that such an $x$ exists, just note that\[P(1,1): f^{f(1)}(1) = f(2)\implies f^{f(1) - 1}(1) = 2\]$\square$ $P(a,1): f^{f(a)}(1) f^2(a) = f(a+1)^2$. $P(a,a): f^{f(a)-1}(a) = 2a$ Claim: $f(3)$ is even. Proof: Suppose that $f(3)$ was odd. $P(2,1)$ gives that $f^{f(2)}(1) = f^{f(2) - 1}(2)$ and $ f(f(2))$ are odd. $P(2,2)$ gives that $f^{f(2) - 1}(2) = 4$, contradiction. $\square$ If $f(3) = 2t$, then $P(t,t): f^{f(t) - 1}(t) =f(3)\implies f^{f(t) - 2}(t) = 3$, which implies $f(m) = 3$ for some $m$. Claim: $m=2$. Proof: Suppose $m>2$. $P(m,m): f^2(m) = 2m$, so $f(3) = 2m$. If $m=3$, then $f(3) = 6$ and $f(3) = 3$, so now assume $m>3$. Notice that if $a+b = m$, then $f^{f(a)}(b) = f^{f(b)}(a) = 3$. This implies that $f^2(m-1) = 3$, so $f(m-1)= k$. Thus, $f^{f(m-1)}(1) = f^m(1) = 3$. We also have $f^{f(m-3)}(3) = 3$, so $3,f(3),f(f(3)), \ldots, $ cycles and thus is bounded. Let $S = \{3, f(3), f(f(3)), \ldots \}$. Using $P(3,3)$, we get $6\in S$. Using $P(6,6)$, we get $12\in S$. Similarly, we may get $2^k\cdot 3\in S$ for any $k$, which is a contradiction because $S$ is bounded. $\square$ So $f(1) = 2$ and $f(2) = 3$. Now we induct to show $f(n) = n+1$ for all $n$. Suppose the result was true for everything less than or equal to $t$ for $t\ge 2$. We will show $f(t+1) = t+2$. $P(t,2): f^{t+1}(2) f^{3}(t) = f(t+2)^2$. Notice that $f^{t-1}(2) = t+1$, so $f^{t+1}(2) = f(f(t+1))$. Notice that $f^3(t) = f(f(t+1))$ also. Thus,\[f(f(t+1)) = f(t+2)\implies f(t+1) = t+2,\]as desired.