Here is my solution Let: $$P(m,n)=f(n)+1400m^2|n^2+f(f(m))$$we have from $P(n,1)$ that $$f(n) \le n^2+f(f(1))-1400$$Lets have : $$g(m,n)(f(n)+1400m^2)=n^2+f(f(m))$$so it is trivial that : $$f(a)+1400m^2 | a^2-n^2+g(m,n)(f(n)-f(a))$$so we have : $$(f(a)+1400m^2)(f(n)+1400m^2) \le (a^2-n^2)(f(n)+1400m^2)+n^2+f(m)^2+f(f(1))-1400$$Which gives that there are $a,b$ such that : $$m^2+f(f(1))-1400 \ge f(m) \ge am^2+b$$Now we have: $$g(m,n)=\frac{1+\frac{f(f(m))}{n^2}}{\frac{f(n)}{n^2}+\frac{1400m^2}{n^2}}$$so for big enough $n$ we have : $$g(m,n)=[\frac{n^2}{f(n)}]$$so we have : $$[\frac{n^2}{f(n)}]f(n)+1400[\frac{n^2}{f(n)}]m^2 \le n^2+f(f(m))$$so for big enough $n$ we have $$f(f(1))-1400[\frac{n^2}{f(n)}]=f(f(2))-1400[\frac{n^2}{f(n)}]4$$so this means for big enough $n$ we have$ [\frac{n^2}{f(n)}]$ is a fixed positive integer. so $$f(f(m))-1400[\frac{n^2}{f(n)}]m^2=C$$which is clearly false. since $$f(f(m))= O(m^4)$$so $$f(f(m))-1400[\frac{n^2}{f(n)}]m^2=O(m^4)$$so it cant be constant.

where can I learn about $O(n)$ ?

Mr.C wrote: so it is trivial that : $$f(a)+1400m^2 | a^2-n^2+g(m,n)(f(n)-f(a))$$so we have : $$(f(a)+1400m^2)(f(n)+1400m^2) \le (a^2-n^2)(f(n)+1400m^2)+n^2+f(m)^2+f(f(1))-1400$$ How to you get inequality directly from the divisibility? What if $RHS$ is negative or even $0$ ? Also $f(n)=f(a)$ could happen.

NTstrucker wrote: Mr.C wrote: so it is trivial that : $$f(a)+1400m^2 | a^2-n^2+g(m,n)(f(n)-f(a))$$so we have : $$(f(a)+1400m^2)(f(n)+1400m^2) \le (a^2-n^2)(f(n)+1400m^2)+n^2+f(m)^2+f(f(1))-1400$$ How to you get inequality directly from the divisibility? What if $RHS$ is negative or even $0$ ? Also $f(n)=f(a)$ could happen. It was trivial enough that i didnt mention it. if $f(a)=f(b)$ we have a contradiction by looking at $$p(a+b,a),p(a+b,b)$$also if it is negative it wont effect us. since we take an absolute value and we only care about the constants that clearly exist

How do you exclude the case $RHS=0$ ?

NTstrucker wrote: How do you exclude the case $RHS=0$ ? There exists $a,n$ such that $$a^2-n^2$$is not divisible by $f(n)-f(a)$ which is enough for us it is getting crowded here if you have other questions or think that i am miss taking in somewhere please write me a dm

Solved with p_square, L567 Let $P(m,n)$ denote the given assertion. $f(n)+1400m^2 \mid n^2 + f(f(m))$ $P(n,1) \Longrightarrow f(n)+1400 \mid n^2+f(f(1)) \Longrightarrow f(n) \leq n^2+f(f(1))-1400$ - (1) $P(f(n),n) \Longrightarrow f(f(n))+1400n^2 \mid f(n)^2+f(f(n)) \Longrightarrow f(n) \geq \sqrt{1400}n$ - (2) Substituting $n=f(m)$ in (1), we get $f(f(m)) \leq f(m)^2+f(f(1))-1400 \leq O(m^4)$-(3) [by (1)] Now let $q(m,n)=\frac{n^2+f(f(m))}{f(n)+1400m^2}$. Substituting $n=m^2$, we get : $q(m,m^2)=\frac{n^2+f(f(m))}{f(n)+1400m^2}=\frac{n^2+f(f(m))}{f(m^2)+1400n}$. Simplifying, we get $n^2-1400q(m,m^2)n+q(m,m^2)f(m^2)-f(f(m))=0$. So now, consider the quadratic polynomial: $$P(x)=x^2-1400q(m,m^2)x+q(m,m^2)f(m^2)-f(f(m))=0$$ From above we know $x=n$ is a root of $P(x)$. Let $u$ be the other root. By Vieta's formulae: $m^2+u=1400q(m,m^2)$ and $m^2u=q(m,m^2)f(m^2)-f(f(m))$. Now suppose $f(n)=O(n^{\alpha})$. By (1),(2), we know $1 \leq \alpha \leq 2$. So $q(m,m^2) \leq O(m^{4-2{\alpha}})$ by (1),(2) and (3). Now if $\alpha >1, 1400 q(m,m^2) < O(m^2)$. So $u=1400q(m,m^2)-m^2<0 \Longrightarrow m^2u<0 \Longrightarrow q(m,m^2)f(m^2)-f(f(m))<0 \Longrightarrow \frac{m^4f(m^2)-1400m^2f(f(m))}{f(m^2)+1400m^2} \leq 0 \Longrightarrow m^2f(m^2) \leq f(f(m))$. But now we have $m^2f(m^2) \geq O(m^{2+2{\alpha}})$ and $f(f(m)) \leq O(m^4)$. So the above can occur only if $2+2{\alpha} \leq 4 \Longrightarrow \alpha \leq 1$. But by our assumption earlier, $\alpha > 1$, a contradiction. $\Longrightarrow \alpha=1$. So $f(n)=O(n)$. But then for large m, $q(m,1)=\frac{1+f(f(m))}{f(1)+1400m^2}=O(\frac{1}{m})$. But then $q(m,1)$ is not an integer, a contradiction to the problem statement. So there are no such functions.

PUjnk wrote: Now suppose $f(n)=O(n^{\alpha})$. You need to first prove that there exists $\alpha$ such that $\lim_{n \to \infty} \frac{f(n)}{n^\alpha} $ exists, before simply assuming this.

It has already been proved that $f(n) \le n^2 + f(f(1)) - 1400 = O(n^2)$ and so such a limit does exist

OK, what I said above is the definition of $\Theta( \cdot) $. But assume that you mean $\mathcal{O} (\cdot)$ , wikipedia says, Wikipedia wrote: Let $f$ be a real or complex valued function and $g$ a real valued function. Let both functions be defined on some unbounded subset of the positive real numbers, and $g(x)$ be strictly positive for all large enough values of $x$. One writes $$ f(x)=\mathcal{O}(g(x)) ~ \text{as} ~ x \to \infty $$ if the absolute value of $f(x)$ is at most a positive constant multiple of $g(x)$ for all sufficiently large values of $x$. That is, $f(x)=\mathcal{O}(g(x))$ if there exists a positive real number $M$ and a real number $x_0$ such that $$ |f(x)|\leq Mg(x) ~ \text{ for all } ~ x\geq x_{0} $$ So the first you assertion you used here cannot be derived, because you don't have a $\ge$ PUjnk wrote: But now we have $m^2f(m^2) \geq O(m^{2+2{\alpha}})$ and $f(f(m)) \leq O(m^4)$.

Here when I am saying $f(n)=O(n^{\alpha})$, I mean there are constants C and D such that $Cn^{\alpha} \leq f(n) \leq Dn^{\alpha}$. So the last assertion works.

If so, you actually mean $\Theta( n^\alpha)$. But please provide a proof to PUjnk wrote: there are constants C and D such that $Cn^{\alpha} \leq f(n) \leq Dn^{\alpha}$

here’s my solution in the exam: Lemma: Let $h,g: N\rightarrow N$, such that $lim _{n\rightarrow \infty} h,g =\infty$ and $\exists k; k>\frac{h(n)}{g(n)^2}$. Then if $a,b,c,d\in N$,There exists $k’$ such that: $$\mid T(n) \mid=\mid \frac{h(n) +a}{g(n)+b}-\frac{h(n)+c}{g(n) +d} \mid <k’$$Proof: $$\mid T(n) \mid =\mid \frac{(d-b)h(n) +(a-c)g(n) +ad-bc}{(g(n)+b)(g(n)+d)} \mid \leq \mid \frac{(d-b)h(n)}{(g(n)+b)(g(n)+d} \mid +\mid \frac{(a-c)g(n)+ad-bc}{(g(n)+b)(g(n)+d)} \mid $$$$\leq |d-b|k +\mid \frac{(a-c)g(n)+ad-bc}{(g(n)+b)(g(n)+d)} \leq |d-b|k +|a-c| +|ad-bc|=k’$$So the lemma is proven Back to the problem: Part 1: taking properties: Let $p(n,m)$ be the assertion of the problem. Setting $p(f(m),m)$ we get $f(f(m))+1400m^2 \mid f(f(m)) f(m)^2$. Knowing that $1400m^2\neq f(m)^2$ we conclude that $f(m)^2 +f(f(m)) \geq 2(f(f(m)) +1400m^2)$ so: $f(m)^2>f(f(m))$ (1) $f(m) >\sqrt{2800} m$ (2) Setting $p(1,m)$ we easily get $f(f(m))>1400m^2$ (3) Setting $p(n,1)$ we get that there is a $l\in R^+$ such that $n^2 >l \cdot f(n)$. (4) If $f(a)=f(b)$ then by checking $p(a,m), p(b,m)$ for large $m$ gives us that $a=b$ so $f$ is injective (5) Part 2: using the lemma: In the lemma, for a constant $n$ and variable $m$ set: $$h= f(f(m)), g=1400m^2, a=n^2, b=f(n), c=(n+1)^2, d=f(n+1)$$The first condition is a direct consequence of (3) and for the second condition: $$g(m)^2 \geq(1400m^2)^2>1400^2 l^2 f(m)^2>1400^2 c^3 f(f(m)) \Rightarrow k>\frac{h(m)}{g(m)^2}$$so the second condition is also true. Now we can use the lemma: $T(m)<k’$ now note that according to $p(n,m), p(n+1,m)$ both fractions that make $T(m)$ are actually natural numbers so $T(m)$ is an integer. Beacuse $T(m)<k’$ then there exists an integer $v$ such that $T(m)=v$ has infinitely many solutions (by the pigeonhole principle). Let $A$ be the set of $m$ such that $T(m)=v$. Let $m\in A$ then: $$\frac{f(f(m))+n^2}{1400m^2 +f(n)} -\frac{f(f(m))+(n+1)^2}{1400m^2 +f(n+1)}=v$$then by rearranging the equality we get that $f(f(m))=am^4+bm^2+c$ where $a,b,c\in Q$ Now we look at $p(n,m)$ for $m\in A$ and any $n$: $f(n)+1400m ^2\mid n^2 am^4+bm^2+c$ so we multiply the right hand side by $1400^2 u$ such that $ua,ub,uc$ are integers so now by replacing any $1400m^2$ in the right hand side with $-f(n)$ we get that: $f(n) +1400m^2\mid r n^2 +a’f(n)^2+ b’f(n) +c’$ Such that $r,a’,b’,c’\in Q$ and $a’=0 \Leftrightarrow a=0$ (It’s easy to check this). By increasing $m$ (Because there are infinitely many such $m$) we get that the right hand side must be 0. So there are $a”,b”,c”\in Q$ such that for all $n$ we have $n^2=a”f(n)^2+b”f(n)+c”$ and $a”=0\Leftrightarrow a=0$ (also easy to check). (6) Now for an $m\in A$ set $f(m)$ and $m$ in (6) and combine: $$m^2=a”(a”(am^4+bm^2+c)^2+b”(am^4+bm^2 +c) +c”) +b”\sqrt{a”(am^4+bm^2+c)^2 +b”(am^4+bm^2+c) +c”} +c”$$Now if $a\neq 0$ then the RHS is degree $8$ so by increasing $m$ we get a contradiction. So $a=0$ then $a”=0$ so: $$m^2= b”\sqrt{b”(bm^2+c) +c”} +c”$$But now the LHS is degree 2 but the RHS is at most degree 1. Still a contradiction. So No such function exists.