Find all functions $f : \mathbb{N}\rightarrow \mathbb{N}$ satisfying following condition: \[f(n+1)>f(f(n)), \quad \forall n \in \mathbb{N}.\]
Problem
Source:
Tags: algebra, Functional inequality, functional equation, IMO 1977, IMO Shortlist, IMO, Hi
21.02.2006 16:13
There are more solution. For example $1) \ f(n)=n,$ $2) \ f(n)=n-(-1)^n,$ and combinations 1), 2).
21.02.2006 18:18
http://www.kalva.demon.co.uk/imo/isoln/isoln776.html
22.02.2006 03:15
Rust wrote: There are more solution. For example $1) \ f(n)=n,$ $2) \ f(n)=n-(-1)^n,$ and combinations 1), 2). The second one doesn't seem to work because the inequality is strict. For instance, take any $n$ odd: $f(n+1) = (n+1)-1 = n$ $f(f(n)) = f(n+1) = n$ so strict inequality does not hold.
24.08.2006 17:18
I have a solution please tell me if I am wrong .We suppose that $f$ is decreasing in an interval $G$ . Then for $k\in G$ we have from ypothesis $f(k+1)>f(f(k))$ so $f(k)>k+1$ so $f(p)>p+1$ for any $p$ in $G$ . So $f(p)=p+m$ where $m$ is a positive integer $m\geq 2$ By hypothesis we find that $p+m+1>p+2m$ or $1>m$ contradiction . So $f$ is an increasing function .So by hypothesis again $f(n+1)>f(f(n))$ implies that $n+1>f(n)$ . But from the fact that $f$ is an increasing function we find that $f(n)\geq n$ so $f(n)=n$
24.08.2006 17:56
silouan wrote: $f$ is decreasing in an interval $G$ . Then for $k\in G$ we have from ypothesis $f(k+1)>f(f(k))$ so $f(k)>k+1$ so $f(p)>p+1$ for any $p$ in $G$ . Exactly for any $p$ in $G$, suth that $f(p)\in G$ and $p+1\in G$.
27.07.2007 07:41
A fairly simple solution is as follows. It assumes that the mapping $ f$ is bijective, and increasing. For the sake of brevity (I'm lazy) those lemmata have been left out. $ f(n+1)>f(f(n))$ We apply the inverse of $ f$ to both sides $ n+1>f(n)$ Similarly, we can say that $ f(n)>f(f(n-1))$ $ \therefore n>f(n-1)$ Putting these together, we get that $ f(n+1)>n>f(n-1)$ This means that $ n+1>f^{-1}(n)>n-1$, but since $ f$ is bijective, $ f^{-1}$ must be an integer between $ n-1$ and $ n+1$ exclusive. Thus $ f^{-1}(n)=n$ $ f(n)=n$ QED
12.07.2012 18:47
I thought this was a new problem and so I posted it elsewhere to share it with others(It was locked and I was referred to this thread).Anyway,I shall post my solution now: Let $r=\text{min}\{f(n):n\in \mathbb{N}\}$ and $m\in \mathbb{N}$ so that $r=f(m)$.For the sake of contradiction, assume that $m>1$.Then $r=f(m)>f(f(m-1))$, which contradicts the minimality of $r$.So, $m=1$ and $f(1)<f(2)$.In the set $\{f(n):n\ge 2\}$,$f(2)$ is the minimum(using the same argument).If $f(1)>1$ then $f(1)\ge 2$.Clearly,$f(f(1))\ge 2$, a contradiction to the initial condition.So, $f(1)=1$.Consider $g(n)=f(n+1)-1$. So, $g(g(n))=g(f(n+1)-1)<f(n+2)-1=g(n+1)$.$g$ satisfies the same condition as $f$.Therefore,$g(1)=1$ and hence $f(2)=2$. By induction on $n$, $f(n)=n$
18.11.2017 08:58
Lemma. If $n\geq m$, then $f(n)\geq m$. Proof. We proceed by induction on $m$. For $m=1$ this is trivial. Suppose $f(n)\geq m$ for all $n\geq m$. If $n\geq m+1$, using the induction hypothesis twice, $$ n-1\geq m\hspace{4mm}\Rightarrow\hspace{4mm}f(n-1)\geq m\hspace{4mm}\Rightarrow\hspace{4mm}f\left(f(n-1)\right)\geq m, $$and it follows that $f(n) > f\left(f(n-1)\right)\geq m$. $\square$ Now, going back to the original question, the lemma implies that $f\left(f(n)\right)\geq f(n)$, so $f(n+1) > f(n)$, i.e., $f$ is strictly increasing. Since $f$ is strictly increasing, $f(n+1) > f\left(f(n)\right)$ implies $n+1 > f(n)$, i.e., $f(n)\leq n$. Combining this with the lemma, which asserts $f(n)\geq n$, we get $f(n) = n$.
16.09.2018 10:49
We claim that the only solution is $f(x)=x$. It is easy to check that this works. We now show that this is the only solution, so suppose $f$ is a solution. Lemma: $f(x)\ge x$. Proof of Lemma: We will prove that $f(x)=n\implies x\le n$. We proceed by strong induction on $n$. Suppose $f(x)=m\implies x\le m$ for all $m<n$. Now suppose $f(x)=n$. We have that $f(x)>f(f(x-1))$, so $f(f(x-1))\le n-1$, so $f(x-1)\le n-1$ by the induction hypothesis. Thus, $x-1\le n-1$ by the induction hypothesis, so $x\le n$. Therefore, the claim is proved. $\blacksquare$ We see $f(n+1)>f(f(n))\ge f(n)$, so $f$ is strictly increasing, so if $a\ge b$, then $f(a)\ge f(b)$. Suppose there was some $n$ with $f(n)\ge n+1$. Then, $f(n+1)>f(f(n))\ge f(n+1)$, a contradiction. Thus, there is no $n$ with $f(n)\ge n+1$, so $f(n)=n$ for all $n\in\mathbb{Z}_{>0}$.
16.09.2018 11:59
It's IMO 1977 P6. See here.
26.05.2019 01:51
The only solution is $f(n) = n$, which we prove by strong induction. Base check: let $a$ be the input for which $f$ is minimized. Suppose for contradiction that $a > 1$. Then substitute $n = a - 1$ into the given inequality to find that an input of $f(a - 1)$ gives a lower output, a contradiction, thus $a = 1$, and $a$ is the only input for which $f$ gives its minimum output (i.e $f$ is injective for this input). We have 3 assumptions: (1) Assume that $f(n) = n \forall n \le k - 1$, (2) that $f$ is injective $\forall$ inputs $n \le k$, and (3) that $f$ takes its $k$th least output at $f(k)$. Let $f(a)$ be the $(k + 1)$th least output of $f$. First, $a > k$ as $f(a) > f(n) \forall n \le k$ and $f$ is injective for these values. Also, by the given inequality, we have $f(f(a - 1)) < f(a)$. But $f(a)$ is the $(k + 1)$th least output of $f$, so $f(f(a - 1))$ is among the $k$ least outputs. For these values, $f$ is injective and $f(n) = n \forall n \le k - 1$. Either $f(f(a - 1))$ gives the $k$th least output or it is among the $k-1$ least outputs. If it is in the $k-1$ least outputs then $1 \le f(a - 1) \le k-1$ which in turn implies that $2 \le a \le k$ which is absurd as $a > k$. Thus $f(f(a - 1))$ gives the $k$th least output of $f$. But we assumed $f(k)$ gives the $k$th lowest output and $f$ is injective here. Thus $f(a - 1) = k$. $\therefore f(a - 1) > k - 1$, so $f(a - 1)$ is at least the $k$th least output of $f$. Also $k > f(n) \forall n < k$ and the $k$th least output of $f$ is $f(k)$. Hence $f(k) = k$, which shows (1) hold for the induction. Also, $f$ is injective here, so $f(a - 1) = k = f(k)$ implies that $a = k + 1$, so the $(k + 1)$th least output of $f$ is $f(k + 1)$, so (3) holds. Also, $f$ is injective at this point (as $a = k + 1$ was the only value of $a$), so (2) holds. This completes the induction, so the only solution is $f(n) = n$
27.08.2019 15:53
We claim that the only solution to this functional equation is $f \equiv n$. Lemma: For all $n \in \mathbb{Z}_{>0}$, $f(n) \ge n$. We will show that for all $k \ge 0$, $n > k$ implies $f(n) > k$, which implies the desired result for $k = n-1$. To show this, we will induct on $k$. Base Case: For $k=0$, this is trivial. Induction Step: Given that $n > k$ implies $f(n) > k$, we will show that $n > k+1$ implies $f(n) > k + 1$. Suppose that $n > k+1$. Since $n-1 > k$, we see that $f(n-1) > k$, and so $f(f(n-1)) > k$. By the given equation, we have that $f(n) > f(f(n-1)) > k$. Since $f$ is a function on the integers and $k$ is an integer, we see that $f(n) \ge f(f(n-1) + 1 \ge k + 2$. Equivalently, $f(n) > k+1$, which is the desired result. $\blacksquare$ Now, we will show that $f$ is monotonically increasing. Suppose this is not the case, that is, suppose that $f(k) \ge f(k+1) > f(f(k))$ for some $k$. By our lemma, we then have that $f(k) > f(f(k)) \ge f(k)$, which is absurd. Thus, we must have that $f(k) < f(k+1)$ for all $k$, so $f$ is monotonically increasing. Since $f$ is monotonically increasing, the given equation implies that $n+1 > f(n)$ for all $n$. However, $f(n) \ge n$ for all $n$ by our lemma. Thus, $f(n)$ must be $n$ for all $n$, as $f$ is defined on the integers.
01.01.2020 00:03
for reference
23.01.2020 19:09
Clearly $f(n)\ge 1$ for all $n\ge 1$. Thus $f(n+1)>f(f(n))\ge 1$ for all $n\ge 1$, so $f(n)\ge 2$ for all $n\ge 2$. So for all $n\ge 2$, $f(n+1)>f(f(n))\ge 2$ (since $f(n)\ge 2$), meaning $f(n)\ge 3$ for all $n\ge 3$. We can keep on going and use induction to show $f(k)\ge k$ for all $n\ge k$. We also have $f(n)\ge n$ for all $n$. Hence, $f(n+1)>f(f(n))\ge f(n)$ for all $n$, meaning $f$ is increasing. Thus, we can "unwrap" $f(n+1)>f(f(n))$ to get $f(n)<n+1$, meaning $f(n)=n$ for all $n$, as desired.
22.03.2020 20:28
IMO 1977, problem 6
12.10.2020 08:08
The solution idea is a weird induct, where we want to prove $f(n) \geq n$. Evidently this holds for $f(1)$. Now for $f(2)$, we can write the inequality $f(2) > f(f(1))$. Since $f$ maps to positive integers, $f(2) > 1$ or equivalently $f(2) \geq 2$. Now for the general case: Assume that $i = 1, 2, \cdots, k - 1$ all satisfy $f(i) \geq i$. Write the inequality $f(k) > f(f(k - 1))$, but by plugging in $n = f(k - 1) - 1$ which is obviously $\geq k - 2$, we get $f(f(k - 1)) > f(f(f(k - 1) - 1))$. The idea is now clear; we continue like this, with the lower bound decreasing by $1$ every single time, and we are done. Now, use $f(x) \geq x$ on the original statement in order to get $f(n + 1) > f(f(n)) \geq f(n)$, or $f(n + 1) > f(n)$, hence $f$ is strictly increasing. Next, assume that $f(k) > k$ for some value of $k$. Then, plugging in $n = k$, we find that $f(k + 1) > f(f(k)) = f(\text{something geq k + 1})$, which is obviously bad. Hence we are done.
29.05.2021 17:57
[I'm not sure if I did an IMO problem, check it please!] Claim 1: $f(n) \ge n$. Proof 1: $f(n)>f(f(n-1))=a_{n-1}>f(f(f(n-1)-1)))=a_{n-2}>...>f(f(f(f(...f(1)-n+1))))=a_1$. By Induction on $n$, $f(n)\ge n$. Claim 2: $f(n)>f(n-1)>...>f(2)>f(1)$. Proof 2: $$f(n)>f(f(n-1))\ge f(n-1)$$. Hence the claim is true. Claim 3: $f(n)=n \forall n$. Proof 3: If $f(n)=n+k$ for some $k\ge 0$. Then, $$2k+n+1\ge f(f(n-1))$$. Since $2k+n+1$ is a possible value it is always less than $f(n)=n+k \implies k<1 \implies k=0 \implies f(n)=n \forall n$.
31.07.2021 00:38
Let $P(n)$ be the given assertion. We first prove by induction that $f(x)\ge x$. For $1$ it is obvious, and the same is true of $2$ since $P(1)\Rightarrow f(2)>f(f(1))\ge1$. Assume that $f(n)\ge n$ for some $n\in\mathbb N$. The induction step folows. Let $a_1=n$ and $a_{i+1}=f(a_i)-1$ for all $1\le i\le n$. First we prove that $\bigcup_{i=1}^n\{a_i\}\subseteq\mathbb N$. Since $a_i\ge0$, it suffices to consider the case where some $j$ satisfies $a_j=0$. Simple induction gives $f(a_{j-t})=t$ for $t<j$, so $f(n)=j-1$. This implies $j\ge n+1$, hence the result. Then: $$P(a_1),P(a_2),\ldots,P(a_n)\Rightarrow f(a_1+1)>f(a_2+1)>\ldots>f(a_n+1).$$Since there are $n-1$ "$>$" signs, we obtain $f(a_1+1)>n$, or $f(n+1)\ge n+1$. This proves that $f(x)\ge x$. $P(n)\Rightarrow f(n+1)>f(f(n))\ge f(n)$, so $f$ is strictly increasing. Then the original assertion implies $f(n)<n+1$, so $\boxed{f(n)=n}$ for each $n$.
18.08.2021 17:13
Here's a wacky solution that I think is really cool. Suppose $f$ works, and consider the function $g(x)=f(x+1)-1$. Observe that $g: \mathbb{N} \to \mathbb{N}$, since if $f(x+1)=1$ for $x \in \mathbb{N}$, we have $1>f(f(x))$ which is absurd. Substituting $g$ into our inequality, we obtain $g(x)+1>g(g(x-1))+1 \implies g(x)>g(g(x-1))$ for $x\geq 2$, which is equivalent to $g(x+1)>g(g(x))$ for $x \in \mathbb{N}$. Hence $g$ also satisfies the inequality. From this, induction gives that $g_k(x)=f(x+k)-k$ is a solution to the inequality for all positive integers $k$. Since $g_k$ is $\mathbb{N} \to \mathbb{N}$, it follows that $f(1+k)-k\geq 1 \implies f(x) \geq x$ for $x\geq 2$. Since it's obvious that $f(1) \geq 1$, it follows that $f(x)\geq x$ for all $x \in \mathbb{N}$. Hence $f(n+1)>f(f(n)) \implies f(n+1)>f(n)$, so $f$ is strictly increasing. Thus $f(n+1)>f(f(n))$ also implies $n+1>f(n) \implies f(x) \leq x$ for all $x \in \mathbb{N}$, so $f(x)=x$ for all $x$, which indeed works. $\blacksquare$
21.08.2021 17:49
I finally solved a P6 Claim: $f$ is strictly increasing Proof. We will start by proving that $f(1)$ is the least value $f$ can take, and that there does not exist $x$ such that $f(x)=f(1)$. Suppose not. Let $f(k+1)$ be the minimum value $f$ can take for some $k \geq 1$. Then note that $f(k+1)>f(f(k))$. This is a contradiction. Now I will prove that $f(2)$ is the minimum value $f$ can take for $\mathbb{N}-\{1\}$. Suppose not. Let $f(k+1)$ be the minimum for $k \geq 2$. Then note that $f(k+1)>f(f(k))$. But $f(k) >1$ since $k \geq 2$. So this is a contradiction. Continuing henceforth, we see that $f$ is increasing $\blacksquare$. Now we clearly have $n+1 > f(n)$. We also have $f(n)>f(n-1)> \dots > f(1)$. Therefore $f(n+1) \geq f(1)+n-1=1+n-1=n$ since $2>f(1) \implies f(1)=1$. $n+1 > f(n) \geq n$ clearly implies $f(n)=n$ which works too $\blacksquare$
24.08.2021 17:35
25.04.2022 20:33
I have my solution to this problem here.
21.01.2023 08:41
Let $m_1,m_2, \ldots$ be a permutation of $1,2, \ldots$ such that $f(m_1) \leq f(m_2) \leq \cdots$. We will prove that $f(k)=k$ for every positive integer $k$, we will prove this by induction. Claim 1: $f(1)=1$ Recall that $f(m_1)$ is minimal. First, we will show that $m_1=1$. Assume for the sake of contradiction that $m_1>1$. We have $f(m_1) > f(f(m_1-1))$ which contradicts minimality. So, $f(1)$ is minimal. Recall $f(m_2)$ is second to minimal. So, \[ f(m_2) > f(f(m_2-1)) \implies f(m_2-1) = 1 \]so, $1$ is in the image of $f$ which must be minimal. Implying that $f(1)=1$ $\square$ Notice that this also implies that $m_2-1=1 \implies m_2 = 2$ Now assume that $f(i)=i$ for all $i \leq k$. We will show that $f(k+1)=k+1$. Notice that $f(m_{k+1}) > f(f(m_{k+1}-1))$ so it must be the case that $f(m_{k+1}-1) \in \{1,2, \ldots, k \}$. This implies that $f(f(m_{k+1}-1)) = f(m_{k+1}-1)$. So, $f(m_{k+1})>f(m_{k+1}-1)$. Thus, it must be the case that $m_{k+1}-1 = m_\ell$ for some $\ell \leq k$. Assume $\ell < k$. Then $m_{k+1}=m_\ell + 1 = m_t$ for some $t \leq k$. Thus, $f(m_{k+1}) = f(m_t) = t$ which contradicts the fact that $f(m_{k+1})$ is the $k+1$'st smallest element in the image of $f$. So, $m_{k+1}-1=m_k$. This pretty easily implies $f(k+1)=k+1$. Completing induction. $\blacksquare$
09.09.2023 21:37
Nice problem. We are given $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $f\left(n+1\right)>f\left(f\left(n\right)\right)$. Clearly, $f\left(n\right)\neq n+1$. Claim 1: if 1 has a pre-image, then it must be 1. Proof. If there exists $n>1$ such that $f\left(n\right)=1$, then $1=f\left(n\right)>f\left(f\left(n-1\right)\right)$, which is a contradiction. So, for $n>1$ then $f\left(n\right)>1$. Claim 2: if 2 has a pre-image, then it must be 2. Proof. Note that $f\left(1\right)\neq2$. Suppose $n>2$ exists, such that $f\left(n\right)=2\Rightarrow2=f\left(n\right)>f\left(f\left(n-1\right)\right)$, forcing $f\left(f\left(n-1\right)\right)=1\Rightarrow f\left(n-1\right)=1\Rightarrow n-1=1\Rightarrow n=2$, a contradiction. Claim 3: $f\left(n\right)\geq n$ for all positive integers $n$. Proof. Let $k=f\left(n\right)$. Using the previous claims as base case/s, the inductive step is as follows: suppose there exists a pre-image of $k$ which is $m>k$. So, $f\left(m\right)=k>f\left(f\left(m-1\right)\right)\Rightarrow f\left(f\left(m-1\right)\right)\le k-1\Rightarrow m=1+f\left(f\left(m-1\right)\right)\le k$, a contradiction. So, pre-image/s of every number is/are less than that number. Hence, $f\left(n\right)\geq n$. Claim 4: if $n$ has a pre-image, then it must be $n$. Proof. Suppose there exists $k\neq n$ such that $f\left(k\right)=n$. Note that $n=f\left(k\right)\geq k$, and $k=n-1$ is not possible since $f\left(n\right)=f\left(k+1\right)>f\left(f\left(k\right)\right)=f\left(n\right)$, a contradiction. So, $k\le n-2$. Suppose $d=n-k\geq2$. Now, \[f\left(n\right)=f\left(f\left(k\right)\right)<f\left(k+1\right)\Rightarrow f\left(k+2\right)>f\left(f\left(k+1\right)\right)\geq f\left(k+1\right)>f\left(n\right)\]\[\Rightarrow f\left(k+3\right)>f\left(f\left(k+2\right)\right)\geq f\left(k+2\right)>f\left(n\right)\]\[\cdots\]\[f\left(n\right)=f\left(k+d\right)>f\left(f\left(k+d-1\right)\right)\geq f\left(k+d-1\right)>f\left(n\right),\]which is a contradiction. So, the pre-image of $n$ must be $n$. As a result, the function must be injective. Moreover, if $n$ does not have a pre-image, then the unique pre-image of $f\left(n\right)$ must be $f\left(n\right)\neq n$, a contradiction. So, the function is surjective as well. Hence, the function is bijective. So, it is the identity function $\boxed{f(n)=n}$.
20.11.2023 05:33
First by induction, $f(k) \geq n$ for all $k\geq n$. The base case $n = 1$ is trivial. For the inductive step, \[ f(n+1) > f(f(n)) \geq f(k) \geq k \]So $f(n+1) \geq k+1$ when $n+1 \geq k+1$. Now, $f(n)$ is increasing. Assume FTSOC that $f(n) \geq f(n+1)$. Then \[ f(n) \geq f(n+1) > f(f(n)) \]which is a contradiction. Finally, note that if $f(n) > n$, then \[ f(n+1) > f(f(n)) \geq f(n+1) \]a contradiction. Thus, it must be that $f(n) = n$. $\blacksquare$
06.02.2024 20:37
09.02.2024 17:18
Define the sequences $\{a_n\}$ and $\{b_n\}$ such that $a_1=t$, $a_n = f(a_{n-1}-1) $, and $b_n = f(a_n)$. Then $\{b_n\}$ is strictly decreasing, so it must terminate. Thus $\{a_n\}$ must also terminate, so 1 must be in this sequence, implying 1 is in the range of $f$. Note that if $r>1$ and $f(r)$ is the lowest value in the range of $f$, $f(r) > f(f(r-1))$ gives a contradiction. Hence $r=1$, and is the only value such that $f(r)=1$. We continue with induction. Suppose for all $j \leq k$, we have $f(x)=j \iff x=j$. Then there must exist some integer $m$ such that \[a_m=1, a_{m-1}=2, \ldots, a_{m-k+1}=k.\] The value of $a_{m-k+1}$ tells us $a_{m-k}=k+1$, so $k+1$ is in the range of $f$. Assume again by contradiction the lowest value in the range of $f$ greater than $k$ is $f(r)$, where $r>k+1$. Then \[f(r-1) > k, f(r) > f(f(r-1)) \implies f(r) > k+1,\] contradiction. Thus $f(x)=k+1 \iff x=k+1$, and we're done. $\blacksquare$
28.02.2024 13:01
We uploaded our solution https://calimath.org/pdf/IMO1977-6.pdf on youtube https://youtu.be/4IQ4c92USgo.
13.03.2024 20:11
Years later this problem still makes me laugh... I will show that $f(n) \geq k$ for all $n \geq k$ by induction on $k$. In particular, the result for $k=1$ is vacuous. Now, observe that for any $n \geq k$, we have $f(n+1) > f(f(n)) = f(\geq k) \geq k$ hence $f(n+1) \geq k+1$, which completes the induction. In particular, this implies that $f(n) \geq n$ for each $n$. Then, let $r$ be the minimum of $f(n)-n$ across all $n$, and suppose $f(k) - k = r$ for some $k$. It follows that $$r+k = f(k) > f(f(k-1)) = f(\geq k-1+r) \geq k-1+2r.$$This forces $r = 0$, so $f \equiv n$.
31.03.2024 19:46
Since $f$ is over the positive integers, there must exist a minimum value of $f(x)$ by the well-ordering principle. However, note that for all $x>1$, we have that \[f(x)>f(f(x-1)),\]meaning that $f(x)$ for $x>1$ cannot possibly take the minimum value of $f$. Therefore $f(1)$ must take the minimum value of $f(x)$ and it must be the only one. Now note that (again by the WOP) there must exist a second-smallest possible value of $f$. However, note again that \[f(x)>f(f(x-1)),\]so if $f(x-1)=k$ such that $k\neq 1$, we have that \[f(x)>f(k)>f(1),\]since $f(1)$ is the unique (meaning if $f(1)=m$, then $f(x)=m$ only has the solution $x=1$) minimum value of $f$. This implies that if $f(x-1)\neq 1$, then $f(x)$ cannot be the second-smallest possible value of $f$. Therefore $f(x-1)=1$. However, this would imply that $f(x-1)$ takes the minimum value of $f(x)$ (since $f$ is over the positive integers), meaning that $x-1=1$. Therefore, we get that \[f(1)=1,\]and \[f(1)<f(2)<f(3),f(4),\dots\]which will become our base case. Now for the inductive step, I claim that if we know \[f(x)=x \forall 1\leq x\leq k-1,\]and \[f(1)<f(2)<\dots<f(k)<f(k+1),f(k+2),\dots,\]then we can conclude that $f(k)=k$. We start by concluding from the latter condition that $f(k)$ is the unique $k$-th smallest possible value of $f(x)$. Now, consider the $(k+1)$-th smallest possible value of $f(x)$ (not necessarily unique), achieved first (smallest possible integer satisfying) at $f(c)$. We have that \[f(c)>f(f(c-1)),\]so if $f(c-1)=m$ so that $m>k$, we get that \[f(c)>f(m)>f(k),\]by our requirement that \[f(1)<f(2)<\dots<f(k)<f(k+1),f(k+2),\dots.\]This then implies that $f(c)$ would not be the $(k+1)$-th smallest possible value of $f(x)$ since if $f(k)$ is the $k$-th, then $f(m)$ would have to be at least the $(k+1)$-th, making $f(c)$ larger than the $(k+1)$-th. Therefore $f(c-1)\leq k$. However, if $f(c-1)=m$ so that $m<k$, since \[f(x)=x \forall 1\leq x\leq k-1,\]and \[f(1)<f(2)<\dots<f(k)<f(k+1),f(k+2),\dots,\]this would mean that $c$ must equal $m+1<k$, which is a contradiction to our requirement that $f(c)$ must be the $(k+1)$-th smallest possible value of $f(x)$. Therefore, $f(c-1)=k$, which in turn must be the unique $k$-th smallest possible value of $f(x)$, implying that $f(k)=k$ and $c=k+1$. Additionally, since $c$ can only be $k+1$, this implies that $f(c)$ is the UNIQUE $(k+1)$-th smallest possible value of $f(x)$. This gives us that \[f(x)=x \forall 1\leq x\leq k,\]and \[f(1)<f(2)<\dots<f(k+1)<f(k+2),f(k+3),\dots,\]allowing us to continue our induction. Since we now have our base case and our inductive step, our induction is complete. This means that \[f(x)=x \forall x\in \mathbb{Z}_{>0},\]finishing the problem.
10.08.2024 13:05
The key idea is that from induction, $$f(n) \ge f^{k+1}(n-k) + k$$. Putting $k = n-1$, $$f(n) \ge f(1)^n + n - 1 \ge n$$$$\implies \boxed{f(n) \ge n}$$. Now let's say $f(k) = m > k$, then $$f(m) \ge f^{m-k+1}(k) + m - k = f^{m-k}(m) + m - k > f^{m-k}(m) \ge f(m),$$contradiction. So $f$ is identity. $\square$
10.09.2024 07:54
Here's a sketch: By induction $f(n+k)\geq f^{k+1}(n)+k$. In particular $f(n)\geq n$ for all $n$. Let $t$ be the smallest integer such that $f(t)>t$, say $f(t)=t+k$ then $$f(t+1)>f(f(t))=f(t+k)\geq t+f^{t+1}(k)\geq t+1,$$thus by induction $f(n)>n$ for all $n\geq t$. In particular $f(f(t))>f(t)$ thus $f(t+1)>f(t)$, by induction we can prove that $f$ is strictly increasing. But we have $f(t+1)>f(t+k)$, which is a contradiction. Thus $f(n)=n$ for all $n$.
05.10.2024 14:56
As there is a strict inequality and the function is from naturals to naturals, we get a sense of least element. For $m>1$, let $f(m)$ be the least element of the set $\{f(1),f(2),....\}$. By the inequality, $f(m) > f(f(m-1))$ but this contradicts the assumption that $f(m)$ is the least, thus $f(1)$ is the least element. Now consider the least element of the set $\{f(2),f(3),....\}$. By the same logic we get $f(2)$ as the least element. Now $f(2) > f(1)$ since $f(2) = f(1)$ implies $f(1) > f(f(1))$ which contradicts the fact that $f(1)$ is the least element. Thus using the same logic again and again, we can say that $f$ is increasing. Note $f(1) \geq 1$ and with the same logic $f(m) \geq m$. Suppose $f(k) \geq k$ for some $k$ then $f(k) \geq k+1$. Thus $f(k+1) < f(f(k))$ (as $f$ is increasing). But this contradicts the inequality that $f(k+1) > f(f(k))$. Thus we conclude that $f(n) = n$ for all $n \in \mathbb{N}$.
29.10.2024 06:54
Claim: We have $f(n) \geq n$ for all $n$. Proof: Call an integer $n$ "bad" if $f(n ) < n$. FTSOC, assume there exists a bad integer and pick one $k$ which minimizes $f(k)$. Clearly, $k > 1$, so the assertion in the problem gives us \[f(k) > f(f(k-1)).\]If $f(k-1) \geq f(k)$, it follows that $f(k-1)$ is bad. This contradicts the minimality of $f(k)$. Therefore, $f(k-1) < f(k)$, so $k-1$ is itself bad, once again contradicting the minimality of $f(k)$. Note that $f$ is strictly increasing since $f(n+1) > f(f(n)) \geq f(n)$. So, comparing the insides of the original equation, it follows that $n+1 > f(n)$, which combines with the claim we proved to imply $f(n) = n$.
16.11.2024 04:07
Xonk, Had to use a hint Claim: $f(n) \ge k$ for $n \ge k$ Profè: We will proceed with induction on $k$. Base case is $k=1$ which is trivial by range of $f$. For the inductive step suppose for $k=1, \dots, c-1$ that $f(n) \ge k$ for $n \ge k$ is true.Then $f(c) \ge f(f(c-1)) +1 \ge c-1+1 = c.$ done. Now observe that $f(n+1) > f(n)$ because $f(n+1) > f(f(n)) \ge f(n)$. Now $f(n+1) > f(f(n))$ gives $n+1 > f(n) \ge n$ or $f(n)=n$ done.
25.01.2025 03:19
Claim: $f(k)=n\geq k,$ proof We induct. Assume there exists some $k\geq2$ such that $f(k) = 1.$ Then, $P(k - 1)\implies 1 > f(f(k - 1))$, which is absurd. Assume for all $n < k, f(n)\geq n$(our induction hypothesis). For the sake of contradiction, assume there exists some $\ell> k$ such that $f(\ell) = k.$ Then, $P(\ell - 1) \implies k = f(\ell) > f(f(\ell - 1)).$ However, this also implies that $f(\ell - 1) < k,$ and so $\ell - 1 < k.$ Thus, $\ell < k + 1,$ which forms our desired contradiction. \qedhere Hence, $f(n + 1) > f(f(n))\geq f(n),$ which tells us that $f$ is strictly increasing. Assume there exists some $n$ such that $f(n) > n.$ Thus, $f(n) \geq n + 1.$ Thus, $f(f(n))\leq f(n + 1),$ which is a contradiction.