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

Find all functions $$f:\mathbb N^*\to \mathbb N^*$$ satisfying:

1. $$f$$ is a strictly increasing function, and
2. $$f(n)^2 = n f(f(n))$$, $$\forall n\in\mathbb N^*$$ .

Suppose we have $$f(a) = f(b).$$ Then \begin{align} f(a)^2 = f(b)^2 &\Rightarrow af(f(a)) = bf(f(b)) \\ &\Rightarrow a = b \end{align} because $$f(f(a)) = f(f(b)) \neq 0$$.

A function $$f:\mathbb N^*\to \mathbb N^*$$ satisfying $$f$$ is a strictly increasing function $$\Rightarrow f(k) \geq k$$.

It is easy to see that$$f(x) = kx$$ satisfies the equation. But are there any other solutions? I have no idea anymore. Hope to get help from everyone. Thanks very much.

## 2 Answers

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

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

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), 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.

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