Zhero wrote: Determine all strictly increasing functions $f: \mathbb{N}\to\mathbb{N}$ satisfying $nf(f(n))=f(n)^2$ for all positive integers $n$. Let $P(n)$ be the assertion $nf(f(n))=f(n)^2$ Notation : in the following $f(n)^k$ is $f(n)$ raised to power $k$ while $f^{k}(n)$ is $f(f(f(... n ...))$, the $k^{th}$ composition. It's easy to show with induction that $f^{k}(n)=\frac{f(n)^k}{n^{k-1}}$ Setting $k$ great enough, we get that $n|f(n)$ and so we can define a function $g(n)=\frac{f(n)}n$ from $\mathbb N\to\mathbb N$. Since $f^{k}(n)=g(n)^kn$ and $f^{k}$ is increasing, we get $g(m)m^{\frac 1k}>g(n)n^{\frac 1k}$ $\forall m>n$ and $\forall k\in\mathbb N$ Setting $k\to+\infty$ in this inequality, we get that $g(n)$ is non decreasing. But $P(n)$ implies $g(ng(n))=g(n)$ $\forall n$ and so $g(ng(n)^k)=g(n)$ and so : If $g(n)=c>1$ for some $n$, then, since non decreasing, $g(m)=c$ $\forall m\ge n$ and so : either $g(n)=1$ $\forall n$ either $g(n)=1$ $\forall n\in[1,a)$ and $g(n)=c$ $\forall n\ge a$ for some positive integers $a$ and $c>1$ Hence the two solutions : First case gives the solution $f(n)=n$, which indeed is a solution. Second case gives the solution $f(n)=n$ $\forall n< a$ and $f(n)=cn$ $\forall n\ge a$, for any positive integers $a$ and $c>1$, which indeed is a solution.

Sorry if I'm missing something ... why isn't $f(n) \equiv an$ ($a \in \mathbb{Z}^+$) a solution?

That is counted when $a=1$ in case 2.

Most probably I am making a mistake.. $nf(f(n))$ is a square, so $f(f(n))=nc^2$ and $f(n)=cn$ Correct?

Assmit wrote: Most probably I am making a mistake.. $nf(f(n))$ is a square, so $f(f(n))=nc^2$ and $f(n)=cn$ Correct? No. Look for example at $n=8$ and $f(f(8))=2$ so that $8f(f(8))=4^2$

The solutions are $f(x)=x$ and $f(x)=x$ if $x\le a$, $f(x)=kx$ if $x>a$. It is easy to check that these work. Suppose $f$ works. We claim that $f^k(n)=n[f(n)/n]^k$. We induct on $k$, with the base case $k=2$ given in the problem. Suppose it's true for $k$, then \[f^{k+1}(n)=f(n)[f(f(n))/f(n)]^k=f(n)[f(n)/n]^k=n[f(n)/n]^{k+1},\]so the claim is true. Note that since $f$ is increasing, so is $f^k$. Thus, if $m<n$, then \[m[f(m)/m]^k<n[f(n)/n]^k\implies f(m)/m<(n/m)^{1/k}f(n)/n.\]This holds true for arbitrarily large $k$, so $g(x)=f(x)/x$ is weakly increasing with $g(1)=f(1)\ge 1$. If $g\equiv 1$, then we get $f(x)=x$. However, the FE re-writes as $g(ng(n))=g(n)$, so if $n$ is the smallest values such that $g(n)=k>1$, then $g(nk)=g(n)$, so $g(n+1)=g(n)=k$, so $g(x)=k$ for all $x\ge n$. This gives the second solution, as desired.

We can check that $f(x)=x$ is a solution, so assume $f\not\equiv x.$ Let $m$ be the smallest positive integer such that $f(m)\ne m.$ $\textbf{Claim: }$ For all $n,$ there is some positive integer $k$ such that $f^{i}(n)=k^{i}n$ for all positive integers $i.$ $\textbf{Proof: }$ Consider the sequence $n,f(n),f(f(n)),\dots.$ Since $nf(f(n))=f(n)^2,$ this sequence must be geometric. If the common ratio is non-integral, then the sequence will eventually become non-integral, which is impossible. Hence, the common ratio is an integer, so we are done. $\blacksquare$ $\textbf{Corollary: }$ $n\mid f(n)$ for all $n.$ $\textbf{Claim: }$ For all $n,$ if $f(n)=kn,$ then $f(n+1)\ge k(n+1).$ $\textbf{Proof: }$ Assume, for the sake of contradiction, that $f(n+1)\le (k-1)(n+1).$ For all $i,$ we have $$(k-1)^{i}(n+1)\ge f^{i}(n+1)>f^{i}(n)=k^{i}n.$$This is impossible for sufficiently large $i,$ so we are done. $\blacksquare$ Now suppose $f(m)=cm$ for some positive integer $c>1.$ The above claim is enough to imply that $f(x)=cx$ for all $x>m.$ Hence, the only solutions are \[ f(x)=x\forall x,\]\[ f(x) = \begin{cases} $x$ & \text{if $x<m$} \\ $cx$ & \text{if $x\ge m$} \end{cases} \]

Claim: The function $g(n)=f(n)/n$ is weakly increasing. Proof: First we show $f^k(n)=\tfrac{f(n)^k}{n^{k-1}}$. Induct on $k$, base case $k=1$ obvious. Now, \[ f^{k+1}(n) = \frac{f(f(n))^k}{f(n)^{k-1}} = \frac{[f(n)^2/n]^k}{f(n)^{k-1}} = \frac{f(n)^{k+1}}{n^k},\]finishing the induction. Now, suppose $a<b$ are two positive integers. Since $f$ is increasing, so is $f^k$. Therefore, \begin{align*} f^k(a)<f^k(b) &\implies \frac{f(a)^k}{a^{k-1}}<\frac{f(b)^k}{b^{k-1}} \implies \frac{f(b)}{f(a)}>\left(\frac{b}{a}\right)^{1-1/k}. \end{align*}Since the sequence $(b/a)^{1-1/k}$ asymptotically approaches $b/a$ as $k$ increases arbitrarily large, and since $f(b)/f(a)$ is greater than each term of this sequence, we must actually have $f(b)/f(a) \ge b/a$. So $f(a)/a \le f(b)/b$, as desired. $\blacksquare$ Claim: If $f(a)>a$, then the chain $a,f(a),f^2(a),\ldots$ is strictly increasing. Proof: Induct on $k\ge 0$ to show $f^{k+1}(a)>f^k(a)$, base case $k=0$ given. We have $f^{k+1}(a)=f^{k}(f(a))>f^k(a)$ since $f^k$ is strictly increasing and $f(a)>a$. $\blacksquare$ Notice that the original FE rearranges to $f(f(n))/f(n) = f(n)/n$. Therefore, \[ \frac{f(n)}{n} = \frac{f(f(n))}{f(n)} = \frac{f(f(f(n)))}{f(f(n)} = \cdots = \frac{f^k(n)}{f^{k-1}(n)} = \cdots. \]If $f(n)/n=1$ for all $n$, then $f(n)=n$. Else, let $n_0$ be the smallest $n$ such that $f(n_0)>n_0$. In particular note that $f(n)=n$ for all $n< n_0$. Then by the second claim, $n_0,f(n_0),f^2(n_0),\ldots$ is strictly increasing, so the above equalities prove $f(n_0)/n_0=f(n)/n$ for all $n\ge n_0$, i.e. $f(n)=cn$ for all $n\ge n_0$. In conclusion, the solutions are \[ f(n)=n, \qquad f(n)=\begin{cases} n&n<n_0 \\ cn&n\ge n_0 \end{cases} \]for any integers $n_0\ge 1$ and $c>1$. (Note that the first solution is not a subset of the second since $c>1$.) It is easy to check that these work.

We will first show by strong induction that $v_{p}(f(kp^a)) \geq a$, if $p$ is a prime. Base: we have that $kpf(f(kp)) = f(kp)^2$. Therefore $p | f(kp)^2$, so $p | f(kp)$, so $v_{p}(f(kp) \geq 1$. Step: we have $kp^af(f(kp^a)) = f(kp^a)^2$. Now, assume that $v_{p}(f(kp^a)) = b, b < a$. Then $v_{p}(LHS) \geq a + b$, as we know that if $v_{p}(x) = b, v_{p}(f(x)) \geq b$. However, $v_{p}(RHS) = 2b < a + b$, a contradiction, so $a \geq b$ and the induction is finished. Now, since $v_{p}(f(n)) \geq v_{p}(n), \forall p | n$, $f(n) | n \forall n$. Now, let $f(1) = k > 1$. Then a quick induction reveals that $f(k^n) = k^{n + 1} \forall n$. Now, for some $j,x$ let $k^x < j < k^{x + 1}$. Then since $f$ is increasing $k^{x+1} < f(j) < k^{x+2}$.In fact, using the notation $f_{y}(n)$ to mean doing the function $f y$ times, $k^{x+y} < f_{y}(j) < k^{x+y+1}$. Now, we will show by induction that $n^{a-1}f_{a}(n) = f(n)^a$. We have that the base is obviously true. Step: let $n^{a-1}f_{a}(n) = f(n)^a$. Then swapping $f(n)$ for $n$ we get $f(n)^{a-1}f_{a+1}(n) = f(f(n))^a, f(n)^{a-1}f_{a+1}(n) = \frac{f(n)^{2a}}{n^a}, n^{a}f_{a+1}(n) = f(n)^{a+1}$. Plugging this in, we get $k^{x+y} < \frac{f(j)^y}{j^{y-1}} < k^{x+y+1}$. Letting $u = \frac{f(y)}{j}$, we get $k^{x+y} < ju^y < k^{x+y+1}$, and it is clear that $u = k$, as otherwise for a large enough $y$ the inequality will not be true. This gives $f(y) = ky$ as a solution $\forall k > 1$. If $f(1) = 1$, let $n$ be the smallest number such that $f(n) = kn, k > 1$. Then by the same arguments as before, $\forall m > n, f(m) = kn$. Therefore, the solutions are $f(n) = kn, \forall k, f(n) = n, n < j, f(n) = cn, c > j, \forall c,j$.

Can someone please check the below solution: The answer is $$f(x) \equiv x ~~;~~ f(x) \equiv \begin{cases} x \qquad & \text{if } x < d \\ cx \qquad & \text{if } x \ge d \end{cases}$$for some constants $c,d \in \mathbb N$. One can verify these work (just consider two cases: $n < d$ and $n \ge d$). Now we prove the above are the only solutions. Suppose $f(x) \not\equiv x$. Choose the least $d \in \mathbb N$ such that $f(d) \ne d$. Claim: $n \mid f(n) ~ \forall ~ n \in \mathbb N$. Proof: Suppose not and let $v_p(n) > v_p(f(n))$. Then using induction we obtain $$v_p \Big(f^k(n) \Big) > v_p \Big(f^{k+1}(n) \Big) ~ \forall ~ k \in \mathbb N$$which would contradict the fact that $v_p(f^k(n)) \ge 1$ for all $k \in \mathbb N$. This proves our claim. $\square$ So now we can write $f(d) = cd$ for some $c \in \mathbb N$ with $c > 1$. An easy induction yields $$f(c^k \cdot d) = c^{k+1} \cdot d ~ \forall ~ k \in \mathbb Z_{\ge 0}$$Now fix any $n > d$. Because of our claim we can write $f(n) = c_0 \cdot n$. Then induction gives $$f(c_0^k \cdot d) = c_0^{k+1} \cdot n ~ \forall ~ k \in \mathbb Z_{\ge 0}$$Consider any operation $\sim ~ \in \{>,<\}$. For any $i,j,k \in \mathbb Z_{\ge 0}$ we have $$c^i \cdot d ~ \sim ~ c_0^j \cdot n ~ \iff ~ c^{i+1} \cdot d \sim c_0^{j+1} \cdot n \iff \cdots \iff c^{i+k} \cdot d ~ \sim ~ c_0^{j+k} \cdot n$$Thus, $$i \cdot \log c + \log d ~ \sim ~ j \cdot \log c_0 + \log n ~ \iff ~ (i+k) \cdot \log c + \log d ~ \sim ~ (j+k) \cdot \log c_0 + \log n$$Hence, $$\boxed{i \cdot \log c - j \cdot \log c_0 ~ \sim ~ \log n - \log d ~ \iff ~ i \cdot \log c - j \cdot \log c_0 ~ \sim ~ (\log n - \log d) + k \cdot (\log c_0 - \log c)}$$FTSOC, $c_0 \ne c$. $c_0 > c$. Fix $\sim$ as $>$ and any $i,j$ such that $i \cdot \log c - j \cdot \log c_0 > \log n - \log d$. Taking $k$ sufficiently large we obtain a contradiction. $c_0 < c$. Fix $\sim$ as $<$ and $i = j =0$. Again, taking $k$ sufficiently large gives a contradiction (here we are using $\log n > \log d$). This completes the proof of the problem. $\blacksquare$

another digraph problem!

The only solutions are $\boxed{f(n) = n}$ and $\boxed{\begin{cases} f(n) = n & \text{if } n<a \\ f(n) = cn & \text{if } n\ge a \\ \end{cases}}$ for any positive integers $a$ and $c>1$. This works. The given equation implies \[\frac{f(n)}{n} = \frac{f(f(n))}{n}, \]so $n,f(n), f(f(n)), \ldots, $ is a geometric sequence with a positive integer common ratio. Let $g(n) = \frac{f(n)}{n}$. Claim: $g$ is nondecreasing Proof: It suffices to show that $g(n+1)\ge g(n)$ for all positive integers $n$. Suppose $g(n+1)< g(n)$ for some $n$. We have $f^k(n) = n \cdot g(n)^k$ and $f^k(n+1) = (n+1)\cdot g(n+1)^k$. Since $f$ is strictly increasing, we have \[(n+1)g(n+1)^k > n g(n)^k,\]so \[\frac{n+1}{n} > \left(\frac{g(n)}{g(n+1)}\right)^k\]Setting $k$ sufficiently large gives a contradiction as $\frac{g(n)}{g(n+1)} > 1$. $\square$ Assume that $f(n)$ is not the identity. Let $a$ be the smallest positive integer such that $g(a) > 1$. Let $g(a) = c $. For $n\ge a$, we have $g(n+1)\ge g(n) \ge c$, so \[f(n+1)\ge f(n) + c\]Since there infinitely many integers $m\ge a$ such that $f(m) = cm$ ($a, f(a), f(f(a)), \ldots$), equality must hold for all $n$. Thus, \[f(n) \ge cn\forall n\ge a,\]as desired.

The condition essentially says that $f(n)$ is the geometric mean of $n$ and $f(f(n))$. This means that $$n,f(n),f(f(n))\cdots$$is a geometric sequence. Therefore, $f(n)$ is divisible by $n$ since otherwise the sequence will eventually have non-integer terms. Define the sequence $k_i$ so that $$f(n)=nk_n.$$We also claim that $k$ is a nondecreasing sequence. Suppose that $a<b$. Then, $$f^n(a)=ak_a^n,f(b)=ak_b^n.$$Suppose FTSOC that $k_a>k_b$. Then, by setting $n$ sufficiently large, we would get that $f^n(a)>f^n(b)$, which contradicts $f$ being increasing. We then claim that the sequence $k_i$ cannot take on two different greater than 1 values. Suppose that $a<b$ and $k_a\neq k_b$, but $k_a,k_b>1$. Note that then $k_a<k_b$. However, we also have that $$k_a=k_{ak_a}=k_{ak_a^2}\cdots,$$and eventually the index will exceed $b$ since $k_a>1.$ However, this means that $k_a\geq k_b$, contradiction. Therefore, the $k$ sequence can only take on one value greater than 1. Therefore, we must have $f(n)=n$ up to some point (possibly 0), and then $f(n)=kn$ after that. All such functions work, so we are done.

Note that $f(n) \ge n$. Rearrange such the equation becomes \[ \frac{f(n)}{n} = \frac{f(f(n))}{f(n)} = \frac{f^{(3)}(n)}{f^{(2)}(n)} = \dots \] Assume that there exists minimal $k$ such $f(k) > k$, else $f$ must be identity. Then, if we let $c = \frac{f(k)}{k}$, by the above it follows that $k \cdot c^a = f^{a}(k)$ for all integers $a$. By taking sufficiently large $a$, it follows that $c$ must be an integer and thus $n \mid f(n)$ for all integers $n$. Furthermore, the above equation means that $f(x) = c \cdot x$ holds for $x = k, c \cdot k, c^2 \cdot k, \dots$ Now consider the range \[ c^{a+1} \cdot k = f(c^a \cdot k) < f(c^a \cdot k + 1) < \dots < f(c^{a+1} \cdot k) = c^{a+2} \cdot k \]for nonnegative integer $a$. Then, since $n \mid f(n)$, it follows that $f(c^a \cdot k + i) \ge c^{a+1} \cdot k + i \cdot a$. The upper bound forces inequality, and varying $a$ gives that $f(x) = c \cdot x$ holds for all $c \ge k$. Thus, $f$ is either the identity or of the form for some positive integers $c, k$ \[ f(x) = \begin{cases} x & x < k \\ c \cdot x & x \ge k \end{cases} \] It can be verified that all such forms also work.

We claim the solution is $f(x)=x$, or $f(x)=x$ for the first $n$ natural numbers then $f(x)=ax$ for the rest of the natural numbers for some $n \in \mathbb Z_{\ge 0}$, and some integer $a>1$. Claim: $x \mid f(x)$ for all $x$ Proof: For each $x$, consider the chain $x, f(x), f(f(x)), f(f(f(x))), \dots$ note that the problem statement implies that these form a geometric sequence, But, due to the range of natural numbers $a$ must be a natural number. So $x \mid f(x)$ as desired. $\square$ Now suppose for the sake of contradiction that their exists some natural numbers $n, m$ such that $f(n)=an$, and $f(m)=bm$ such that $m>n$ and $b>a>1$, . Choose a positive integer $k$ such that $a^{k}n >bm$. Then $f(a^kn)=a^{k+1}n$. Also note that $f(a^kn)>ba^kn$ but this implies $b<a$ contradiction. Q.E.D.

Choose a positive integer $m$ and a positive integer $r$. Then the functions are \[f(n)=\begin{cases}n&n<m\\rn&n\ge m\end{cases}.\] Note that $n,f(n),f(f(n)),f(f(f(n))),\dots$ forms an infinite geometric sequence, so the common ratio must be an integer. If $f$ is the identity, this works. Otherwise, let $m$ be the minimum positive integer that has $f(m)>m$. Then let the common ratio for $m$ be $r$, so $f(m)=mr$, $f(mr)=mr^2$, etc. Therefore, any nonconstant sequence must have a common ratio of at least $r$ (otherwise it would fall behind and not be strictly increasing), but any nonconstant sequence also must have a common ratio at most $r$ (otherwise the sequence containing $m$ would fall behind). Therefore, every nonconstant sequence has a common ratio of exactly $r$. You can't have nonconstant sequences anymore past $m$, and before it it has to be constant (by the definition of $m$), so we are done. $\blacksquare$