1

Question: Let $f(x): N → N$ be a strictly increasing function, where $N$ is denoted as the set of all positive integers. If $f(f(n)) = 3n$, what is a possible value of $f(1)$?

My approach (Cases) :

  1. $f(1) = 1$: Starting to eliminate some possible values for $f(1),$ we realize that $f(1)$ is not equal to $1$, because otherwise $f(f(1)) = 1$, but according to the problem, it would have to be $3$. Since $1$ is not equal to $3$, $f(1)$ is not equal to $1$.

  2. $f(2) = 2$: There is nothing wrong with $f(2) = 2$ because it satisfies the strictly increasing part and it also doesn't have a problem with $f(f(2)) = 6$, although I could be wrong.

  3. $f(3) = 3$: $f(f(n)) = 9$... what to do?

I am very confused from this point onwards because I don't know how to use the fact that $f(x)$ is a strictly increasing function, or what to do with the $f(f(n)) = 3n$. Maybe I could use the $N$ is the set of all positive integers? I don't know.

Any help would be appreciated, thank you!

I am a person
  • 1,084

2 Answers2

2

$f$ strictly increasing means that $f(n)<f(n+1)$. Most of the proof follows from this.

As you have said, $f(1)\neq 1$ since if $f(1)=1$ then $f(f(1))=f(1)=1$ but we require $f(f(1))=3$. So $f(1)>1$.

Now if $f(1)>2$ then $f(2)>3$ (since $f$ is strictly increasing) so $f(f(1))>f(2)>3$ although we again require $f(f(1))=3$.

So we have discounted, by contradiction, every possibility except $f(1)=2$

Adrian Savage
  • 309
1

Notice that since $f$ is a strictly increasing positive-integer-valued function, that means $x\leq f(x)$ for all $x$. This is because $f(1)$ is at least $1$, so $f(2)$ is at least $2$, and so on.

So $f(f(n))=3n$ must be at least $f(n)$.

So $f(f(1))=3$ must be at least $f(1)$. So $f(1)\leq 3.$

MathTrain
  • 2,147