2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Is there anything you tried to solve this before posting here? For example, do you know $f(1)$, $f(2)$ and $f(3)$? $\endgroup$ – Hetebrij Apr 7 '16 at 10:25
  • 1
    $\begingroup$ Please try to avoid posting simple equations as images or image links. You can write equations using MathJax markup, eg, your equation can be written as $(n-1)^2 < f(n) \cdot f(f(n)) < n^2 + n$ $\endgroup$ – PM 2Ring Apr 7 '16 at 10:30
  • $\begingroup$ Even if you don't know the MathJax syntax, there's no character in your equation that you can't simply type on your keyboard. There really is no excuse for hiding them behind an image. $\endgroup$ – Henning Makholm Apr 7 '16 at 10:34
  • $\begingroup$ @HenningMakholm looks better now, I guess. $\endgroup$ – jack jones Apr 7 '16 at 10:41
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.