# Find the function satisfying conditions. Is my method valid?

This problem is a modified version of a problem from Australian mathematics competition 1984:

The problem is let $f:\mathbb Z^+ \to \mathbb Z^+$ be a function from positive integers to positive integers which satisfy the following three conditions.

1. $f(2)=2$
2. $f(mn)=f(m) f(n)$ for $m,n \in \mathbb Z^+$
3. If $m>n$ then $f(m)>f(n)$ for $m,n \in \mathbb Z^+$

Find such an $f$ and prove it is the only function satisfying the above 3 conditions.

It can be proved $f(n)=n$ by induction very easily.

An alternative attempt would be:

Suppose $f(n)=A_1+A_2n+A_3n^2+A_4n^3+ \cdots$. Then, $$f(n \cdot n)=A_1+A_2n^2+A_3n^4+A_4n^6+...=(A_1+A_2n+A_3n^2+A_4n^3+...)^2 ,$$ and by compairing coefficents of similer powers of $n$s it can be showen that $A_i=0$ for $i\in {\mathbb Z^+-\{ 2 \} }$ and $A_2=1$ which leads to $f(n)=n$.

My problem is:

Is this alternative method valid, since it supposes the function to be polynomial but the expected function can be any function (which can't be expressed as a polynomial)? I have a doubt that this is not a valid method to prove this is the only function.

• Yes, the second approach ignores any function that cannot be expressed in that series form. – angryavian May 26 '18 at 19:36
• Not exactly a polynomial since there may be infinitely many terms, but yes, your intuition is correct. – Arnaud Mortier May 26 '18 at 19:40

If at all, the second approach uses only the fact that $$f(n^2)=f(n)^2$$ There are many functions with this much weaker property, hence any proof that shows $f(n)=n$ for all $n$ on these grounds is faulty.
E.g., if we define $f(n)=nu^{17}$ where $u$ is the largest odd divisor of $n$, we have $f(n^2)=f(n)^2$ (and even $f(nm)=f(n)f(m)$) as well as $f(2)=2$, but the third condition of the problem statement (monotonicity) is broken.
• Thank you. by the way, L.H.S of the series is taken by putting $n^2$ to $f$. – Gune May 26 '18 at 19:51