Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function such that $f(n+1)>f(n)$ and $f(f(n))=3 n$ for all $n$. Evaluate $f(2001)$
- $f\left(3^{n}\right)=2 \cdot 3^{n} ;$ and
- $f\left(2 \cdot 3^{n}\right)=3^{n+1}$
First they prove this 2 lemmas by induction and then
" There are $3^{n}-1$ integers $m$ such that $3^{n}<m<2 \cdot 3^{n}$ and there are $3^{n}-1$ integers $m^{\prime}$ such that $$ f\left(3^{n}\right)=2 \cdot 3^{n}<m^{\prime}<3^{n+1}=f\left(2 \cdot 3^{n}\right) $$ since $f$ is an increasing function, $$ f\left(3^{n}+m\right)=2 \cdot 3^{n}+m $$ for $0 \leq m \leq 3^{n} .$
I did not get this last part ,how they got $$ f\left(3^{n}+m\right)=2 \cdot 3^{n}+m $$
thankyou
Suppose $g$ is an increasing function on the integers, and I tell you that $g(5) = 8, g(9) = 12$.
Then you know that for $n = 6, 7, 8$, the values $g(n)$ have to be between $8$ and $12$ (it's an increasing function), and there are exactly 3 such possible values (namely $9, 10, 11$). So $g(6) = 9, g(7) = 10, g(8) = 11$ (again, because it's an increasing function).
That's what's going on here: between $f(3^n)$ and $f(2\cdot 3^n)$, you have exactly $3^n-1$ integers, and they have to be associated to exactly $3^n - 1$ domain values, and they have to do so in increasing order. There's only one choice! As the argument to $f$ increases by $1$, the output must also increase by at least one (it's increasing!) and at most one (or there won't be enough room for all the outputs to fit).