An induction problem

Given $f:\Bbb{N} \rightarrow \Bbb{N}\,$ That satisfies all of the stated conditions.

  1. $ f(m*n)=f(m)*f(n)$
  2. $f(2) = 2$
  3. $m>n \rightarrow f(m) > f(n)$

I need to prove that $\forall\,n\in\,\Bbb{N}\quad\,f(n) = n$


closed as off-topic by José Carlos Santos, Namaste, Xander Henderson, Saad, jvdhooft Jun 10 '18 at 7:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – José Carlos Santos, Namaste, Xander Henderson, Saad, jvdhooft
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Have you proved it for any values of $n$ yet? $\endgroup$ – aschepler Jun 9 '18 at 22:36
  • $\begingroup$ what do you mean, the conditions are given. I checked it for n =1 and its true but I have no idea how to proceed. $\endgroup$ – gabi939 Jun 9 '18 at 22:38
  • $\begingroup$ How about $n=4$? $\endgroup$ – aschepler Jun 9 '18 at 22:41
  • $\begingroup$ its true for n= 4 $\endgroup$ – gabi939 Jun 9 '18 at 22:42

$$f(1 * 1)=f(1) * f(1) \implies f(1)=1,$$ next $$f(2 * 2)=f(2) * f(2) \implies f(4)=4,$$ next $$f(4)> f(3) > f(2) \implies f(3)=3.$$ Can you proceed? Hint: Use strong induction!

  • $\begingroup$ Thank you very much I understand what I need to do $\endgroup$ – gabi939 Jun 9 '18 at 22:46

In case you or someone else gets stuck at some step.

$4\geq f(4)>f(3)>f(2)=2$. Therefore, $f(3)=3$.

Assume that $p>2$ is prime and for all primes $q<p$ we have $f(q)=q$. In particular $f(n)=n$ for all $n$ divisible only by primes $<p$.

Let $q$ be the next prime after $p$. Then $q+1=2\frac{q+1}{2}$ and $\frac{q+1}{2}$ is $<q$ and therefore divisible only by primes $<p$. Therefore, $f(p+1)=f(2\frac{q+1}{2})=f(2)f(\frac{q+1}{2})=2\frac{q+1}{2}=q+1$.

It follows that $q+1=f(q+1)>f(q)>f(q-1)=q-1$, where the last equality is due to $q-1$ being divisible only by primes $<p$. Therefore $f(q+1)=q+1$.

By induction on the primes $f(q)=q$ for all primes. Since the function is completely multiplicative, then $f(n)=n$ for all $n\in\mathbb{N}$.


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