Functional equation $(n-1)^2 < f(n) f(f(n)) < n^2 +n$.

Question

Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that $$(n-1)^2 < f(n) f(f(n)) < n^2 +n$$ for all $n \in \mathbb{N}$.

Answer 1

We show by induction that any function $f\colon \mathbb N\rightarrow \mathbb N$ satisfying $$ (n-1)^2< f(n)\cdot f(f(n)) < n^2+n\quad \text{for all $n\in\mathbb N$} \tag{1} $$ is necessarily the identity function.

Let $f$ be a function satisfying (1). For $n=1$ we have $$ 0 < f(1)\cdot f(f(1)) < 2, $$ i. e. $f(1)\cdot f(f(1)) = 1$, i. e. $f(1)=1$.

Now, assume $f(k)=k$ for $k<n$. We have to show that $f(n)=n$.

• Assume for a contradiction, that $m:= f(n)\le n-1$. Then $$ f(n)\cdot f(f(n)) = m\cdot f(m) = m^2 \le (n-1)^2 $$ contradicting $(n-1)^2 < f(n)\cdot f(f(n))$. Hence $f(n)\ge n$.

• Assume for a contradiction, that $m:= f(n) > n$. Then $$ m\cdot f(m) = f(n)\cdot f(f(n)) < n^2+n = n(n+1). $$ Now, $m>n$ implies $f(m)< n+1$, i. e. $f(m) \le n$.

  • If $f(m)<n$, then $f(m)\le m-1$ and by induction hypothesis for $f(m)$ $$ f(m)\cdot f(f(m)) = f(m)^2 \le (m-1)^2 $$ contradicting (1) for $m$.
  • If $f(m) = n$, then by (1) for $n$ $$ mn = f(n)\cdot f(f(n)) < (n+1)n, $$ and hence $m<n+1$, contradicting $m>n$.

Hence also the case $f(n)>n$ leads to a contradiction. It follows that $f(n)=n$.