my solution = we show that $f(n)=n$ is the only such function. the base case of $n=1$ implies $f(1)f(f(1))=1$ so $f(1)=1$ now suppose $f(n)=m$ for $m<n$ and $f(n)\ne n$ now if $f(n)\leq n-1$ than $f(n)f(f(n)\leq (n-1)^2$ since $f(n)=f(f(n))$ we get $f(n)^2\ge (n-1)^2$ which is a contradiction. now suppose on other hand that $f(n)\ge n+1$ than $(n+1)f(f(n))\leq f(n)f(f(n)<n^2+n$ and thus $f(f(n))<n$ and thus $f(f(f(n)))=f(f(n))$ and now $f(f(n))^2< n^2\leq (f(n)-1)^2$ which is again a contradiction. hence we get that $f(n)=n$ for all $n$.

This is a nice introductory olympiad problem! My solution below seems similar to the two above mine, but is more detailed/verbose I guess. I claim that $f(n)=n$ is the only such function that works. Use strong induction. For our base case, remark that from $0<f(1)f(f(1))<2$ we get $f(1)f(f(1))=1$, so $f(1)=1$. Now assume that $f(i)=i$ for each $1\leq i\leq k-1$. In order to evaluate $f(k)$, we bound, and to do this we split up the proof into two distinct cases. CASE 1: Suppose $f(k)<k$. Let $f(k)=k_0$; then by the induction hypothesis $f(k_0)=k_0$. But since $k_0$ is a positive integer we must have $k_0\leq k-1$, so \[f(k)f(f(k))=k_0f(k_0)=k_0^2<(k-1)^2,\] which contradicts the problem statement. Hence $f(k)\geq k$. CASE 2: Suppose $f(k)>k$. Once again, let $f(k)=k_0$. Unfortunately, we are not able to derive $f(k_0)=k_0$ from this because the inductive hypothesis does not stretch up to $f(k_0)$. To tackle this, we once again split into cases. If $f(k_0)\geq k$, then a simple bounding argument reveals that \[f(k)f(f(k))=k_0f(k_0)\geq k_0k\geq (k+1)k=k^2+k,\] contradiction. If $f(k_0)<k$, then let $f(k_0)=k_1$. We cannot necessarily deduce anything from plugging in $n=k$ into the problem statement functional equation, but now consider what happens when $n=k_1$. In this case, an argument analogous to CASE 1 occurs: we have \[f(k_0)f(f(k_0))=k_1f(k_1)=k_1^2<(k_0-1)^2,\] contradiction. In conclusion, we must have $f(k)=k$, so by the Principle of Strong Induction we can conclude that $\boxed{f(n)=n}$ is the only solution to the functional equation.

We prove by strong induction on $n$ that $f(k) = n$ if and only if $k = n$. For the base case $n=1$, we have $0 < f(1)f(f(1)) < 2$, which forces $f(1) = 1 = f(f(1))$. Furthermore, if $f(k)=1$, then $(k-1)^2 < f(k)f(f(k)) = 1 \cdot f(1) = 1$, forcing $k=1$. Now suppose the statement holds for all $1 \le n \le m$. We prove that $f(k) = m+1$ if and only if $k=m+1$. First, write \[m^2 < f(m+1)f(f(m+1)) < (m+1)(m+2).\]By the inductive hypothesis, $f(m+1) \ge m+1$, and thus $f(f(m+1)) \ge m+1$ also. But then the upper bound forces $f(m+1) = m+1 = f(f(m+1))$. Now, suppose $f(k)=m+1$ for some $k$. By the inductive hypothesis, $k \ge m+1$. But now \[(k-1)^2 \le f(k)f(f(k)) = (m+1)f(m+1) = (m+1)^2\]which gives $k \le m+1$. This forces $k=m+1$. The induction is now complete, so $f(n) = n$ is the only function that works (and it is easy to check that it does).

First I prove that if $f(a)=f(b)$ then $|a-b|<2$. To show this , assume that $a \geq b+2$ $$ \Rightarrow (b+1)^2 \leq (a-1)^2<f(a)f(f(a))=f(b)f(f(b))<b^2+b$$$\Longrightarrow (b+1)^2<b^2+b$ a contradiction.$(1)$ Now we use strong induction to prove $f(n)=n$. (The base case has been mentioned in other solutions and we assume that $\forall k = {1,...,n-1}; f(k)=k$) Since we have $(n-1)^2< f(n)f(f(n))$ we know that either $f(n)$ or $f(f(n))$ is more than or equal to $n$. On the other hand we have $ f(n)f(f(n)) < n^2+n$ thus either $f(n)$ or $f(f(n))$ is less than or equal to $n$ so now we’ll have 4 cases. case 1. $f(n)\geq n$ & $f(n) \leq n$ $\Longrightarrow f(n)=n$ problem is solved. case 2. $f(f(n)) \geq n$ & $f(f(n)) \leq n$ $ \Longrightarrow f(f(n))=n$ $\Longrightarrow f(n)f(f(n))<n(n+1) \Longrightarrow f(n) < n+1 $ if $f(n)=n$ problem is solved & if $f(n)=a<n$ then by using induction hypothesis $n=f(f(n))=f(a)=a$ a contradiction. case 3. $f(n)=a<n$ & $f(f(n))>n$ by using induction hypothesis $\Longrightarrow n<f(f(n))=f(a)=a$ a contradiction. case 4. $f(n)>n $ & $f(f(n))=a<n$ by using induction hypothesis $\Longrightarrow f(f(n))=f(f(a)) $ then using $(1)$ we get that $|f(n)-f(a)|<2$ but since $f(n) \geq n+1$ & $f(a)=a \leq n-1$ we get a contradiction.

Here is my step in the strong induction. Suppose that we have $f(x)=x$ for $x < n$, let us show $f(n)=n$. First, we will show that $f(m) \geq n$ for $m \geq n$. Suppose that for some $m$ that's at least $n$ we have $n > f(m)$. Then $f(f(m)) \leq n-1$ from the induction so we have $f(m)f(f(m)) \leq (n-1)^2 \leq (m-1)^2$ which is a contradiction. Now, substituting $n$ for $m$ we get $f(n) \geq n$, but if $f(n) > n$ then $f(f(n)) \geq n$ so $f(n)f(f(n)) \geq (n+1)*n=n^2+n$ which is a contradiction. Hence the only possibility is $f(n)=n$. Really a fun beginner problem on the use of induction in FE! I recommend anyone who liked this problem to solve IMO 1977 P6: https://artofproblemsolving.com/community/c6t239179f6h75980_function , the problems are very similar.

Wonderful problem Someone please check my solution $0<f(1)f(f(1))<2$, thus, $f(1)=1$. We claim that $f(x)=x$ for all positive integers $x$ We proceed by strong induction. Let $f(n)=n$ for $n=1,2,3,\dots,k-1$. We prove that $f(k)=k$. Case 1- Assume $f(k)<k$ Then, $f(k)\leq k-1$ which in turn implies $(k-1)^2<f(k)\cdot f(f(k))\leq (k-1) f(f(k))\longrightarrow f(f(k))>k-1$ But $f(k)\leq k-1$ implies $f(f(k))>f(k)$ which is a contradiction since $f(k)\leq (k-1)$ Case 2- Assume $f(k)>k$. $f(k)\geq k+1$ $k(k+1)>f(k)\cdot f(f(k))\geq (k+1)\cdot f(f(k)) \longrightarrow f(f(k))<k$ $k^2 \leq (f(k)-1)^2 <f(f(k)) \cdot f(f(f(k)))<k \cdot f(f(f(k))) \longrightarrow f(f(f(k)))>k $ Thus $f(f(f(k)))>k>f(f(k))$ which is a contradiction since $f(f(k))<k$. Thus, we can conclude $f(k)=k$ and our induction argument is complete.

We claim only the identity function works. We proceed with strong induction, with base case $0 < f(1)f(f(1)) < 2\implies f(1) = 1$. For the induction step, suppose for some positive integer $m > 1$ that $f(n) = n$ for all $n < m$. Claim: $f(n)\ge m$ for all $n\ge m$. Proof: Suppose FTSOC that $f(n) < m$ for some $n\ge m$. Then $f(n)f(f(n)) = f(n)^2\le (m-1)^2$, a contradiction. Now suppose FTSOC that $f(m) > m$. Then $f(m)f(f(m)) \ge mf(m)\ge m(m+1)$, a contradiction. But then $f(m)\ge m$ and $f(m)\le m$, so $f(m) = m$ and the induction step is complete. Edit: This is almost identical to post #7, oh well.

Strong Induction

$f(n)=n$ satisfies the given equation. We prove that this is the only solution. $n=1$ in given equation gives $f(1)f(f(1))=1$ and hence $f(1)=1 $ We prove by strong induction, with base case $n=1$ shown earlier. Induction hypothesis : Let $f(x)=x$ for $x=1, 2, \cdots ,n-1 $ Consider $f(n) $. There are 3 cases: Case 1: $f(n)<n $ Then, $f(f(n))=f(n)$ by Induction hypothesis. Also, $(n-1)^2<f(n)f(f(n))=f(n)^2 \Rightarrow n-1 < f(n) $ But there is no integer between $ n $ and $n-1$ . Contradiction. Case2 : $f(n)>n$ Hence, $f(n) \ge n+1 $ Hence, $ f(n)f(f(n)) \ge (n+1)f(f(n)) $ But $ n^2+n > f(n)f(f(n)) $ Hence, $ n^2+n >(n+1)f(f(n)) \Rightarrow n >f(f(n)) $ Hence, using Induction Hypothesis $ f(f(f(n))) = f(f(n)) < n $ Also, for $f(n)$, we get that $ \left(f(k)-1\right)^2 < f(f(n))f(f(f(n))) $ But, $ f(f(n))f(f(f(n))) < n\times n =n^2 $ Hence, $ \left(f(n)-1\right)^2 < n^2 \Rightarrow f(n)<n+1 $ But there is no integer between $ n $ and $n+1$ . Contradiction. Hence , combining both cases, we get that $f(n)=n$, which completes the induction. $ \blacksquare $

Setting $n=1$ gives $f(1)f(f(1))=1\Rightarrow f(1)=1$. Assume that $f(k)=k$ for all $k<n$, where $2\le n\in\mathbb N$. Suppose first that $f(n)<n$, then $f(f(n))=f(n)$ so: $$(n-1)^2<f(n)f(f(n))=f(n)^2<n^2$$which is impossible. But, if $f(n)\ge n$ we get: $$n^2+n>f(n)f(f(n))\ge nf(f(n))\Rightarrow f(f(n))\le n.$$If $f(f(n))<n$ then: $$(f(n)-1)^2<f(f(n))f(f(f(n)))=f(f(n))^2<n^2\Rightarrow f(n)<n+1\Rightarrow f(n)=n$$which gives a contradiction. So $f(f(n))=n$, then $nf(n)<n^2+n$ which leads to $f(n)<n+1$, and so $f(n)=n$. By strong induction $\boxed{f(n)=n}$ for all $n$, which is indeed a solution.

Note that $f(1)=1$ by $n=1.$ Assume $f(x)=x$ for all $x<m.$ If $f(M)=\epsilon$ for some $\epsilon<m\leq M$ then setting $n=M$ gives $M<\epsilon$, impossible. Hence $f(M)\geq m$ for all $M\geq m.$ Thus $f(m)\geq m.$ Assume $f(m)>m$ then $f(f(m))<m$ which implies $f(f(m))=f(f(f(m))).$ Setting $n=f(m)$ we get contradiction. It's easy to verify the identity works.

Clearly $f(1)=1$, We prove with induction on $n$ that $f(n)=n$ if $f(n) \textless n$ then $f(f(n)) = f(n)$, this forces $f(n)=n$ if $f(n) \textgreater n$ then $f(f(n))>f(n) > n$ forcing $f(n)f(f(n)) > n^2+n$ $\therefore f(n)=n$ for $n \in \mathbb{N}$

I claim $f(n) = n$ for all $n \in N$ is the only solution to the given equation. We have $f(1)f(f(1)) = 1 \implies f(1) = f(f(1)) = 1$. Now, let's prove by induction. The base case is already proved, let's assume result for all $n \le k$, and prove for $k + 1$. Note that $k^2 < f(k + 1)f(f(k + 1)) < (k + 1)(k + 2).$ Now, if $f(k + 1) < k + 1$, by inductive hypothesis, we have $f(f(k + 1)) = f(k + 1),$ so $f(k + 1)f(f(k + 1)) = f(k + 1)^2 \le k^2,$ a contradiction. On the other hand, if $f(k + 1) > k + 1$, we have $f(k + 1) \ge k + 2$, so we have $f(f(k + 1)) < k + 1$ (by RHS of inequality), but we also have $(f(k + 1) - 1)^2 < f(f(k + 1))f(f(f(k + 1))) < f(k + 1)(f(k + 1) + 1),$ but by inductive hypothesis we have $f(f(f(k + 1))) = f(f(k + 1)),$ but since $(f(k + 1) - 1)^2 < f(f(k + 1))^2,$ which gives $f(f(k + 1)) \ge f(k + 1),$ a contradiction. So, $f(k + 1) = k + 1$, and we're done.

We claim the only such function is $f(n) = n \forall n \in \mathbb{N}$. It is easy to see that this function does work, as $(n-1)^2 < n^2 < n^2 + n$. Now we prove this is the only solution. (For the solution let $P(n)$ denote the given assertion.) We prove the statement using strong induction. Base case ($n = 1$): $P(1)$ gives us $0<f(1)f(f(1)) < 2$, i.e. $f(1) = f(f(1)) = 1$. Inductive step: Let $f(i) = i \forall i \in \{1, 2, \cdots, n \}$. We try to prove that $f(m+1) = m+1$. Claim 1: $f(m+1) \ge m+1$. Proof: Assume FTSOC that $f(m+1) = k < m$. Then $f(m+1)f(f(m+1)) = k^2 >= m^2$. But $m^2 < f(m+1)f(f(m+1))$. Contradiction. Claim 2: $f(m+1) < m+2$. Proof: Assume FTSOC that $f(m+1) \ge m+2$. Then we have $(m+1)^2 + m+1 = m^2 + 3m + 2 > f(m+1)f(f(m+1)) \ge (m+2) f(f(m+1))$ $\implies f(f(m+1)) < m+1$ However, $(f(m+1)-1)^2 < f(f(m+1))f(f(f(m+1))) < (m+1)^2$ $\implies f(m+1) - 1 < m+1 \implies f(m+1) < m+2$, contradiction. From claim 1 and claim 2, we have $f(m+1) = m+1$, QED.

Let $P(n)$ denote the assertion $(n-1)^2<f(n)f(f(n))<n^2+n$. We will show that $f(n)=n$ by strong induction. $P(1) \implies 0<f(1)f(f(1))<2 \implies f(1)f(f(1))=1 \implies f(1)=1$. Note that if $f(n)=1$, we have $(n-1)^2<1 \implies n=1$. Now for $k>1$, assume $f(n)=n$ $\forall n<k$. If $f(k)<k$, then $(k-1)^2<f(k)f(f(k))=f(k)^2<k^2$ which is not possible. If $f(k) \geq k+1$, then $(k+1)f(f(k)) \leq f(k)f(f(k))<k^2+k \implies f(f(k))<k$. Then $f(f(f(k)))=f(f(k)) \leq k-1$, so $(f(k)-1)^2<f(f(k))f(f(f(k))) \leq (k-1)^2 \implies f(k)<k$, contradiction. It follows that $f(k)=k$. We may check that for all $n$, $(n-1)^2<n^2<n^2+n$, so $f(n)=n$ satisfies the equation.

Plugging in $n=1$ gives $0<f(1)f(f(1))<2$ so $f(1)=f(f(1))=1$. We claim that $f(n)=n$ for all $n$. Assume that $f(k)=k$ for all $1\le k\le n-1$. We will prove that $f(n)=n$. Notice that $(n-1)^2<f(n)f(f(n))<n^2+n$. If $f(n)\le n-1$, then $f(f(n))=f(n)$ so $f(n)f(f(n))=f(n)^2\le (n-1)^2$, which is bad. If $f(n)\ge n+1$, then $f(f(n))< \frac{n^2+n}{n+1}=n$ so $f(f(n))\le n-1$. This means that $f(f(f(n)))=f(f(n))$. Therefore, $f(f(n))f(f(f(n)))=f(f(n))^2\le (n-1)^2$. However, since $f(n)\ge n+1$, we must have that $n^2<f(f(n))f(f(f(n)))$, which is clearly impossible. Therefore $f(x)=x$ by induction.