Find all function $f(n)$ satisfying $f(n)^2 = n f(f(n))$

Solution 1:

If $f(n) = k_n n$, then $(k_n n)^2 = n f(k_n n)$, so $f(k_n n) = k_n^2 n = k_n (k_n n)$. Inductively, therefore, $f(k_n^r n) = k_n^{r+1} n$. And $k_n$ has to be an integer: if it weren't, then there would be some integer $r \geq 0$ such that $k_n^r n$ was an integer but $f(k_n^r n) = k_n^{r+1} n$ wasn't.

Write $g(n) = f(n)/n$, giving $k_n$ as a function of $n$. Now let's proceed through some simple deductions.

1. If $g(n) = k \geq 2$ for some $n$, then $g(n) = k$ for an infinite set of values of $n$. Proof: if $k = g(n)$ then $k = g(kn) = g(k^2 n) = g(k^3 n) = \cdots$.

2. If $g(n) = k \geq 2$ for some $n$, then $g(n) = k$ for all sufficiently large $n$. Proof: $k$ occurs infinitely often as a value of $g$. Suppose there were arbitrarily large values of $n$ such that $g(n) \geq k+1$ but $g(n+1) \leq k$. Then $f(n) \geq kn + n$ and $f(n+1) \leq kn + k$, contradicting monotonicity of $f$ if $n \geq k$. So $g$ is eventually bounded above by $k$. Similarly, if there were arbitrarily large values of $n$ such that $g(n-1) \geq k$ and $g(n) \leq k - 1$, then $f(n-1) \geq kn-k$ and $f(n) \leq kn - n$, again contradicting monotonicity if $n \geq k$. So $g$ is eventually bounded below by $k$ as well.

3. $g(n)$ can take at most one value other than $1$. Proof: Any value of $g(n)$ other than $1$ must eventually become the constant value of $g$, and there can only be one such value.

So either $f$ is the identity, or $f(n)$ is either $n$ or $kn$ for some fixed constant $k$ (but whether $f(n) = n$ or $f(n) = kn$ can depend on $n$). In the latter case, monotonicity is broken if $f(n) = kn$ and $f(n+1) = n + 1$, giving the result in Max's answer that $f(n) = n$ for all integers $n < N$ and $f(n) = kn$ for $n \geq N$, for some choice of positive integers $k$ and $N$.

Solution 2:

Proposition: Either $f$ is the identity, or there exist integers $k>1$ and $N\geq 1$ such that

$$f(n)= \begin{cases}n \text{ if } n<N\\kn \text{ if } n\geq N\end{cases}.$$

Proof: We can check that all such $f$ satisfy the conditions (they are positive-integer valued, strictly increasing, and satisfy the functional equation).

We want to show that they are the only ones.

Let $g(n)=\frac{f(n)}{n}$ (on the same domain $\mathbb{N}^*$). The equation says $g(n)=g(f(n))$.

From monotonicity, $g(n)\geq 1$ for all $n$. Let $N_1$ be the minimal $n$ such that $g(n)>1$. We want to prove that $g(n)=g(N_1)=k$ for all $n\geq N_1$. This is equivalent to the statement in the proposition.

Now the proof.

Lemma 1: Suppose for some $N$ we have $g(N)=k>1$, i.e. $f(N)=kN$. Then $f(k^pN)=k^{p+1}N$ for all powers $p\geq 0$.

Proof of Lemma 1: By induction on $p$. The base case is one of the assumptions, and the induction step is given by applying $g(f(n))=g(n)$ to $n=k^pN$. QED

We note that this implies that $k^pN$ is an integer for all $p$, and so $k$ is an integer.

We put $g(N_1)=k_1>1$. Suppose there exists $N_2>N_1$ with $g(N_2)=k_2\neq k_1$. Firstly, by monotonicity of $f$ and the fact that $f(N_1)=k_1N_1>N_1$ with strict inequality, we get $f(N_2)>N_2$ (strictly) so $k_2>1$. Now by Lemma 1, $f(k_1^{p_1}N_1)=k_1^{p+1}N_1$ and $f(k_2^{p_2}N_2)=k_2^{p+1}N_2$ for all non-negative powers $p_1$ and $p_2$. But if $k_1\neq k_2$ this will eventually contradict monotonicity.

Lemma 2: Suppose $k_2>k_1>1$ and $N_1, N_2$ some positive integers. Then we there exist $p_1, p_2$ such that $N_1 k_1^{p_1}\geq N_2 k_2^{p_2}$ but $N_1 k_1^{p_1+1}<N_2 k_2^{p_2+1}$.

We postpone the proof to observe that Lemma 2 implies the proposition. Indeed, it says that if there exists $N_2, N_2$ with $g(N_1)=k_1>1$, $g(N_2)=k_2>1$ with $k_1\neq k_2$ then after possibly swapping indexes 1 and 2, we find ourselves in the situation of Lemma 2, which produces two numbers ($x=N_1 k_1^{p_1}$ and $y=N_2 k_2^{p_2}$) with $x\geq y$, and $f(x)<f(y)$, contradicting monotonicity of $f$.

This completes the proof modulo proving Lemma 2.

Proof of Lemma 2: Taking logs this is equivalent to

$$\ln N_1 +p_1 \ln k_1 \geq \ln N_2 +p_2 \ln k_2$$

but $$\ln N_1 +(p_1+1) \ln k_1 <\ln N_2 +(p_2+1) \ln k_2$$

or

$$ p_1 \ln k_1 -p_2 \ln k_2\geq \ln N_2-\ln N_1>(p_1 \ln k_1 -p_2 \ln k_2)+(\ln k_1-\ln k_2)$$

There are two cases to consider:

1. $\ln k_1$ and $\ln k_2$ are rationally dependent, $\ln k_1=\frac{m}{n}\ln k_2$ for some reduced fraction $\frac{m}{n}$. Then the set of combinations $p_1\ln k_1-p_2 \ln k_2$ with $p_1, p_2\geq 0$ is the same as the set of combinations $p_1\ln k_1-p_2 \ln k_2$ with $p_1, p_2$ arbitrary integers, and by Euclid's algorithm, is a set of multiples of $\Delta=\frac{1}{n}\ln k_2$. Any number $x$, including the number $x=\ln N_2-\ln N_1$, falls between two consecutive such multiples: $ (l-1) \Delta< x\leq l \Delta$, and so there are positive $p_1,p_2$ with $p_1\ln k_1-p_2\ln k_2 -(\frac{1}{n}\ln k_2) < x\leq p_1\ln k_1-p_2\ln k_2$ which together with $(\frac{1}{n}\ln k_2)<\ln k_2-\ln k_1$ yields what we want.

2. $\ln k_1$ and $\ln k_2$ are rationally independent. Then the set of combinations $p_1\ln k_1-p_2\ln k_2$ with non-negative $p_1, p_2$ is dense in the real numbers (this is a "standard fact"; by rescaling it's equivalent to $\{na\}$ being dense in $[0,1]$ for irrational $a$, see, for example, For an irrational number $a$ the fractional part of $na$ for $n\in\mathbb N$ is dense in $[0,1]$). Thus we can find such a combination between $x=\ln N_2-\ln N_1$ and $x+\ln k_2-\ln k_1$, which also gives what we want.