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.

  • 4
    $\begingroup$ Yes, the second approach ignores any function that cannot be expressed in that series form. $\endgroup$ – angryavian May 26 '18 at 19:36
  • 1
    $\begingroup$ Not exactly a polynomial since there may be infinitely many terms, but yes, your intuition is correct. $\endgroup$ – 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.


Your second approach is not valid for the reason you state. There are many functions that can not be expressed as power series.

  • $\begingroup$ Thank you. by the way, L.H.S of the series is taken by putting $n^2$ to $f$. $\endgroup$ – Gune May 26 '18 at 19:51
  • $\begingroup$ OK, I see that. $\endgroup$ – Ross Millikan May 26 '18 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.