nf(f(n)) = f(n)^2, f : N->N

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

nf(f(n)) = f(n)^2, f : N->N

G H J

Reveal topic tags

algebra proposed

L

G H BBookmark kLocked kLocked NReply

Source: ELMO Shortlist 2010, A1; also ELMO #4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2043 posts

Zhero

#1 h Jul 5, 2012, 1:16 AM • 8 Y

Y by Amir Hossein, v_Enhance, Feridimo, MathWizard237, Isluna, megarnie, Adventure10, Mango247

Determine all strictly increasing functions $f: \mathbb{N}\to\mathbb{N}$ satisfying $nf(f(n))=f(n)^2$ for all positive integers $n$ .

Carl Lian and Brian Hamrick.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23464 posts

pco

#2 h Jul 5, 2012, 7:54 AM • 16 Y

Y by Amir Hossein, MinatoF, DwyerX, andria, toto1234567890, LJQ, enhanced, opptoinfinity, MathbugAOPS, MathWizard237, A-Thought-Of-God, megarnie, guptaamitu1, Adventure10, Mango247, Upwgs_2008

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6012 posts

MSTang

#3 h Jun 16, 2015, 4:30 PM • 3 Y

Y by MathWizard237, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1791 posts

#4 h Jun 16, 2015, 7:15 PM • 4 Y

Y by MSTang, MathWizard237, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

970 posts

Gh324

#6 h Jun 4, 2018, 6:41 AM • 3 Y

Y by MathWizard237, Adventure10, Mango247

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

Correct?

This post has been edited 1 time. Last edited by Gh324, Jun 4, 2018, 6:47 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23464 posts

pco

#7 h Jun 4, 2018, 7:57 AM • 2 Y

Y by MathWizard237, Adventure10

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#8 h Aug 18, 2019, 8:43 AM • 4 Y

Y by MathWizard237, guptaamitu1, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

779 posts

#9 h Aug 1, 2020, 5:40 PM • 5 Y

Y by MathWizard237, primesarespecial, Mango247, Mango247, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#11 h Sep 1, 2020, 10:30 PM • 1 Y

Y by A-Thought-Of-God

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.

Remarks

This post has been edited 1 time. Last edited by pad, Sep 1, 2020, 10:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

91 posts

#12 h Jun 1, 2021, 4:51 PM • 1 Y

Y by Mango247

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

This post has been edited 1 time. Last edited by Number1048576, Jun 1, 2021, 4:53 PM
Reason: Proof reading

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7308 posts

DottedCaculator

#14 h Sep 29, 2021, 5:46 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

656 posts

#15 h Oct 16, 2021, 10:27 PM

Y by

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$

This post has been edited 1 time. Last edited by guptaamitu1, Apr 9, 2022, 4:19 PM
Reason: fixing typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1601 posts

#17 h Dec 5, 2022, 5:10 AM

Y by

another digraph problem!
solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5538 posts

#18 h Jan 18, 2023, 1:04 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4171 posts

#19 h Jan 24, 2023, 8:25 PM

Y by

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.

This post has been edited 2 times. Last edited by john0512, Jan 24, 2023, 8:26 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1497 posts

#20 h Apr 28, 2023, 5:37 PM

Y by

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.

This post has been edited 2 times. Last edited by YaoAOPS, Dec 2, 2023, 12:25 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

987 posts

bjump

#21 h Apr 10, 2024, 11:57 PM

Y by

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.

This post has been edited 1 time. Last edited by bjump, Apr 10, 2024, 11:59 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1869 posts

#22 h Apr 11, 2024, 7:21 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

304 posts

#23 h Mar 8, 2025, 4:32 AM

Y by

The answer is $f\equiv\begin{cases} x & x < n \\ cx & x \geq n \end{cases}$
Using induction, we can get $f^k(n) = n(\frac{f(n)}n)^k.$ If $m < n,$
$f^k(m) < f^k(n) \implies m(\frac{f(m)}m)^k<n(\frac{f(n)}n)^k \implies \frac{f(m)}m < \left(\frac nm\right)^{\frac1k}\frac{f(n)}n$ Hence, if $g \equiv \frac fn,$ we get $\frac{g(n)}{g(m)} > \left(\frac mn\right)^{1k},$ which approaches 1. Thus, $g$ is weakly increasing.

We can rewrite the given fe as $g(ng(n)) = g(n).$ Thus, if $g(n) = k > 1,$ then $g(nk^\ell) = n,$ and thus, $g(x) = k$ for $x > n.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#24 h Mar 17, 2025, 9:18 PM

Y by

Let $N$ and $c$ be positive integers. The answers are given by $f(n) = n$ for $n < N$ and $f(n) = cn$ for all $n \geq N$ ; it is not hard to show that these functions work.

To prove that these are the only functions, let $N$ denote the smallest positive integer such that $f(N) \neq N$ , which implies $f(N) > N$ .

Claim: There exists a positive integer $c$ such that $f\left(c^n N\right) = c^{n+1}N$ for all nonnegative integers $n$ .

Proof: Let $f(N) = k$ . Then it is not hard to prove by induction that $f^n(n) = \frac{k^n}{N^{n-1}}$ , which implies that $N^{n-1}$ divides $k^n$ for all positive integers $n$ , i.e. $N$ divides $k$ . Letting $k = cN$ , comparing the values of $f^n(n)$ and $f^{n+1}(n)$ yields $f\left(c^n N\right) = c^{n+1}N$ , as needed. $\blacksquare$

Now, suppose that there exists a positive integer $m > N$ such that $f(m) = c'm$ for some $c' \neq c$ ; then $f\left(c'^n m\right) = c'^{n+1}m$ for all $n$ . We split into cases now:

If $c' < c$ , there must exist a positive integer $n$ such that $c'^n m$ and $c'^{n+1}m$ both fall within the interval $\left[c^k N, c^{k+1} N\right)$ for some $k$ . Then $f\left(c'^n m\right) = c'^{n+1} m < c^{k+1} N = f\left(c^k N\right)$ but $c'^n m \geq c^k N$ , which is a contradiction.
If $c' > c$ , there must exist a positive integer $n$ such that two values $c^k N$ and $c^{k+1}N$ fall within the interval $\left[c'^n m, c'^{n+1}m\right]$ , and we can repeat the above argument analogous.y

Thus we have a contradiction, and it follows $f(m) = cm$ for all $m > N$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a