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
User335559
14.04.2017 20:47
Is $RHS f^2(a+b)$ or $f((a+b)^2)$?
62861
14.04.2017 23:09
Let $P(a, b)$ denote the assertion $f^{f(a)}(b) f^{f(b)}(a) = f(a + b)^2$ for all positive integers $a$ and $b$.
$P(a, a)$ gives $f^{f(a)}(a) = f(2a)$, or $f^{f(a) - 1}(a) = 2a$ since $f$ is injective.
Suppose there existed a $k$ with $f(k) = 1$. Then, $P(k, k)$ gives $f^0(k) = 2k$, i.e. $k = 2k$, which is impossible. Thus, $f(a) \ge 2$ for all $a$, so $f\left(f^{f(a) - 2}(a) \right) = 2a$ for all $a$. Thus, all even positive integers are in the range of $f$.
For every positive integer $n$, define
\[S_n = \{n, f(n), f(f(n)), \dots\}.\]Then, the result above gives that $2n \in S_n$ for all $n$. By an easy induction, we see that $2^k n \in S_n$ for all $k \ge 0$, so $S_n$ is infinite for all $n$.
Suppose $n$ and $k > 0$ are such that $f^k(n) = n$. Then, $S_n$ is finite, a contradiction to the above. Thus, $f^k(n) \neq n$ for all $n$ and $k > 0$.
We know that there exists a positive integer $k$ with $f(k) = 2$. Then, $f^{f(k) - 1}(k) = 2k$, or $2k = f^{f(k) - 1}(k) = f^1(k) = 2$, so $k = 1$. Thus, $f(1) = 2$.
Next, we show that $f(2) = 3$ and $f(3) = 4$. We know that there exists an integer $a \ge 1$ with $f(a + 1) = 4$. Then, $P(1, a)$ gives
\[f(f(a)) f^{f(a)}(1) = f(a + 1)^2 = 16.\]We know that $f(f(a)) \neq 1$, and if $f(f(a)) = 2$, then $f(a) = 1$, a contradiction. Thus, $f(f(a)) \ge 4$.
Similarly, $f^{f(a)}(1) \neq 1$, and if $f^{f(a)}(1) = 2$, then $f^{f(a) - 1}(1) = 1$, so $f(a) = 1$, a contradiction. Thus, $f^{f(a)}(1) \ge 4$.
These two inequalities force $f(f(a)) = f^{f(a)}(1) = 4$. Since $f(a + 1) = 4$, we get $f(a) = a + 1$. In addition, $f^{f(a)}(1) = 4$, or $f^{f(a) - 1}(2) = 4$. However, from $P(2, 2)$, we get $f^{f(2) - 1}(2) = 4$, so $f(a) = f(2)$ and $a = 2$. Finally, $f(a) = a + 1$, so $f(2) = 3$. Thus, $f(2) = 3$ and $f(a + 1) = f(3) = 4$.
Now, we prove that $f(n) = n + 1$ by induction on $n$. The base cases $f(n) = n + 1$ for $n \le 3$ have been done above.
Suppose that $f(n) = n + 1$ for all $n \le 2k - 1$, with $k \ge 2$. We will show that $f(2k) = 2k + 1$ and $f(2k + 1) = 2k + 2$.
Let $a \ge 1$ be an integer with $f(a + 1) = 2k + 2$. Then, $P(1, a)$ gives
\[f(f(a)) f^{f(a)}(1) = f(a + 1)^2 = (2k + 2)^2.\]
Suppose that $f(f(a)) = r \le 2k$. Then $f(a) = r - 1$ and $a = r - 2$, so $f^{f(a)}(1) = f^{r - 1}(1) = r$, since $r - 1 \le 2k - 1$. Then, $r^2 = (2k + 2)^2$, so $r = 2k + 2$, a contradiction. Thus, $f(f(a)) \ge 2k + 1$. However, since $2k + 1 \nmid (2k + 2)^2$, we have $f(f(a)) \ge 2k + 2$.
Suppose that $f^{f(a)}(1) = r \le 2k$. Then, since $f^{r - 1}(1) = r$, we get $f(a) = r - 1$, so $a = r - 2$, and similarly to the above, we get $f(f(a)) = r$ and $r = 2k + 2$, a contradiction. Thus, $f^{f(a)}(1) \ge 2k + 1$, and since $2k + 1 \nmid (2k + 2)^2$, we get $f^{f(a)}(1) \ge 2k + 2$.
The above inequalities force $f(f(a)) = f^{f(a)}(1) = 2k + 2$. Recall that $f(a + 1) = 2k + 2$ as well, so $f(a) = a + 1$.
However, from $P(k + 1, k + 1)$, we know that $f^{f(k + 1) - 1}(k + 1) = 2k + 2$. Since $k + 1 \le 2k - 1$ (as $k \ge 2$), we see that $f(k + 1) = k + 2$, so $f^{k + 1}(k + 1) = 2k + 2$.
However, we see that
\[f^{k - 1}(k + 1) = f^{k - 2}(k + 2) = \dots = f(2k - 1) = 2k,\]so $2k + 2 = f^{k + 1}(k + 1) = f(f(2k))$. Since $f(a + 1) = 2k + 2$, we see that $f(2k) = a + 1$. Since $f(a) = a + 1$ as well, we see that $a = 2k$, so $f(2k) = 2k + 1$ and $f(2k + 1) = 2k + 2$.
The induction is complete, so the only possible function is $f(n) = n + 1$ for all $n$. Since this forces $f^{f(a)}(b) = f^{f(b)}(a) = f(a + b) = a + b + 1$ for all $a$ and $b$, this function is valid.
gradysocool
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...
YaWNeeT
15.04.2017 17:08
Is there any other solution if we don't assume it's injective?
FEcreater
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 $$
suli
16.04.2017 04:42
First plug in $a = b$ and square root both sides to get
$$f^{f(a)} (a) = f(2a).$$By injectivity, this implies $f(a) > 1$ for all $a$ and
$$f^{f(a) - 1} (a) = 2a. \qquad (*)$$In particular, every positive even integer is in the range of $f$.
Let $n$ be the unique $n$ such that $f(n) = 2$. Then we get from $(*)$ that
$$f(n) = 2n \rightarrow n = 1.$$Thus $f(1) = 2$. Now let $n$ be the unique $n$ such that $f(n) = 4$. Then we get from $(*)$ that
$$f^{f(2) - 1} (2) = 4,$$but also plug in $a = 3, b = 1$ in original to get
$$f^{f(n-1)} (1) \cdot f^2 (n-1) = 16.$$Remark that if $f(f(m)) = 2$ for some $m$, then $f(m) = 1$ by injectivity, which is impossible (as established above). Thus since $f(n-1) \ge 2$, none of $f^{f(n-1)} (1)$ and $f^2 (n-1)$ can be $1$ or $2$, so they are both $4$. This gives
$$f^{f(n-1)} (1) = 4 = f^{f(2) - 1} (2) = f^{f(2)} (1).$$By injectivity, this implies $f(n-1) = f(2)$, so $n-1 = 2$, or $n = 3$. Thus $f(3) = 4$. But also $f^2 (n - 1) = 4$, so $f(f(2)) = 4 = f(3)$, so $f(2) = 3$.
To summarize, we have $f(1) = 2, f(2) = 3, f(3) = 4.$ We will prove by strong induction on $n$ with step size $2$ that $f(n) = n+1$.
Base case. $n = 1, 2, 3$ already established.
Inductive step. Suppose $f(k) = k+1$ for all $k < n$, where $n \ge 4$ is even.
Let $m$ be the unique $m$ such that $f(m) = n + 2$. Now plug in $a = m - 1$ and $b = 1$ to get
$$f^{f(m-1)} (1) \cdot f^2 (m-1) = (n + 2)^2. \qquad (**)$$Now suppose $f^2 (m - 1) < n + 2$. Because $n + 1 \mid (n+2)^2 - 1$, we have $n + 1 \nmid (n+2)^2$, so $f^2 (m - 1) \le n$. Let $f^2 (m - 1) = t$. By inductive hypothesis $t = f(t - 1)$, so by injectivity $f(m - 1) = t - 1$. Thus $f^{f(m-1)} (1) = f^{t-1} (1) = t$ by applying the inductive hypothesis. It is clear then that $(**)$ cannot hold since $LHS < RHS$.
A similar contradiction holds if $f^{f(m-1)} (1) < n+2$, so in fact $f^{f(m-1)} (1) \ge n+2$ and $f^2 (m-1) \ge n+2$. Thus they are both equal to $n + 2$, so
$$f^{f(m-1)} (1) = n + 2 = f^{f((n+2)/2) - 1} ((n+2)/2) = f^{(n+2)/2 + n/2} (1),$$applying the inductive hypothesis again in the last step. Thus by injectivity, we have
$$f(m-1) = n + 1.$$Since $f(f(m-1)) = n+2$, we have $f(n+1) = n + 2 = f(m)$, so $m = n + 1$. Thus $f(n) = n + 1$ and $f(n+1) = n + 2$, completing the inductive step and thus the proof that $f(n) = n + 1$ for all $n \ge 1$. Indeed, this is a solution.
niyu
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$
AnyndChe
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$.
IndoMathXdZ
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.
fukano_2
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.
Orestis_Lignos
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.
guptaamitu1
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$
CANBANKAN
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.
megarnie
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.